Khác với lần trước, một hòn đảo khác với vô số đá quý. Trên hòn đảo bây giờ có N loại đá quý. Loại thứ i có trọng lượng là wi có giá trị là vi và có số lượng là ai. Khác với lần trước túi "năm trăm gang" có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý có thể mang về là bao nhiêu?
Input:
•    Dòng đầu tiên ghi hai số N và M (1≤N,N≤1000).
•    N dòng tiếp theo, dòng thứ i ghi ba số wi,vi,ai lần lượt là trọng lượng, giá trị và số lượng của loại đá quý thứ i (0≤ wi,vi,ai  ≤10^3)
Output:
•    Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.
Example:
input
Copy
3 4 
1 4 2 
2 7 2 
3 6 1   
output
Copy
15
C++ 

Giải thích ý tưởng nx nhé

Ý 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;
}