問題描述
在冒險島的深處，小萌探索到了一個傳說中的魔法果實園。這里滿是各種神奇的魔法果實，吃了可以增加不同的魔法能量。
小萌想帶一些魔法果實回去，但是他的背包空間有限。看著這些琳瑯滿目的魔法果實，小萌很是糾結，決定選擇一些最有價值的果實帶回去。
小萌對果園里的魔法果實進行了整理，他發現每種果實都有一顆或者多顆。他估算了下每種魔法果實能增加的魔法能量，然后開始了篩選工作：小萌有一個最大容量為?W?的背包，果園里總共有?n?種魔法果實，每種果實能增加的魔法能量為?vi?，重量為?wi?，每種魔法果實有?mi??顆。小萌希望在背包不超重的前提下，選擇一些魔法果實裝進背包，使得他們能增加的魔法能量最大。
輸入格式
第一行為一個整數?n?和?W，分別表示魔法果實種數和背包的最大容量。
接下來?n?行每行三個整數?vi?,wi?,mi?，分別表示每種果實能增加的魔法能量，重量，每種魔法果實顆數。
輸出格式
輸出僅一個整數，表示在背包不超重的情況下收集的魔法果實能增加的最大魔法能量。
樣例輸入
2 4
2 3 2
1 2 3
樣例輸出
2
說明
樣例中，最優方案是：
第一種魔法果實?1?個，能量?2。第二種魔法果實?0?個，能量?0。最大能量為?2。
或者，第一種魔法果實?0?個，能量?0。第二種魔法果實?2?個，能量?2。最大能量為?2。
因此，最大魔法能量為?2。
評測數據規模
對于?50% 的評測數據，n≤∑mi?≤104，0≤W≤103。
對于 100% 的評測數據，n≤∑mi?≤105，0≤W≤4×104，1≤n≤100。
運行限制
| 語言 | 最大運行時間 | 最大運行內存 |
|---|---|---|
| C++ | 2s | 128M |
| C | 2s | 128M |
| Java | 3s | 128M |
| Python3 | 4s | 128M |
| PyPy3 | 4s | 128M |
| Go | 4s | 128M |
| JavaScript | 4s | 128M |
代碼：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MAX = 4e4 + 4;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dp[MAX];
ll w[MAX], v[MAX], s[MAX];
int main()
{ll N, V;cin >> N >> V;for (int i = 1; i <= N; i++){cin >> v[i] >> w[i] >> s[i];}for (int i = 1; i <= N; i++){for (int j = V; j >=0; j--){for (int k = 0; k <= s[i] && k * w[i] <= j; k++){dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);}}}cout << dp[V] << endl;return 0;
}?
