Ý tưởng

- Dạng: Quy hoạch động(dynamic)

- Độ khó: O($n^{2}$ )

Cách 1:

Cách suy nghĩ rất đơn giản giống bài cái túi bình thường (chọn 1 vật 1 lần).

Cách 2

- Phân tích ra dạng tổng bit (+ dư) để tối ưu, ta thấy rõ việc 10 = 1 + 2 + 4 + 3

   ta có tổng là 10 thì:

1 = 1;

2 = 2;

3 = 2 + 1;

4 = 4;

5 = 4 + 1;

6 = 4 + 2;

7 = 4 + 3;

8 = 4 + 3 + 1;

9 = 4 + 3 + 2;

10 = 1 + 2 + 4 + 3

Code

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;

int dp[MAX_N + 1][MAX_M + 1];

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> w(N), v(N), a(N);

    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i] >> a[i];
    }

    for (int i = 0; i < N; i++) 
        for (int j = 0; j <= M; j++)
            for (int k = 0; k <= a[i]; k++)
                if (j >= k * w[i])
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - k * w[i]] + k * v[i]); else break ; 
    cout << dp[N][M] << endl;

    return 0;
}