Ý tưởng

Nếu bạn không hiểu, bạn có thể hỏi

Ta gọi f[i] là số cách để tạo ra i kg chỉ bằng 2 túi đã cho

Dễ thấy, f[0] = 1 (vì ta chẳng cần túi nào để đựng cả), f[i] = 0 nếu i < 0 (vì ta không thể tạo ra khối lượng âm bằng các túi có khối lượng dương)

Ta lại có: f[i] = f[i-a] + f[i-b]. Tại sao? Do ta luôn có thể tạo ra i kg từ i-a kg bởi ta chỉ cần cho thêm 1 túi a kg vào. Ta có được f[i-a] cách do ta chỉ có 1 cách duy nhất để tạo ra i từ i-a Tương tự với i-b.

Vậy ta có thể mang được một khối lượng m lớn nhất về khi nào? Khi f[m] > 0. Mà m <= n và m phải lớn nhất (do không thể đựng m kg vào thùng chứa n kg được) => Ta sẽ duyệt từng f[i] với i từ n -> 0, nếu f[i] > 0 ta lập tức in ra kết quả và thoát khỏi vòng lặp. Cách duyệt như vậy sẽ luôn đảm bảo sẽ in ra kết quả do f[0] = 1

Để ý thêm 1 điều nữa: Chúng ta không cần quan tâm đến số cách để tạo ra i kg, vì vậy ta có thể biến mảng f[i] thành mảng boolean, với mỗi giá trị f[i] là khả năng tạo ra i kg.

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;

int n,a,b;
bool dp[maxn];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> a >> b;
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        if(i >= a) dp[i] = dp[i-a];
        if(i >= b) dp[i] = (dp[i] || dp[i-b]);
    }
    while(n >= 0){
        if(dp[n]){
            cout << n; return 0;
        }
        n--;
    }
    return 0;
}