P1776 宝物筛选 80分

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
int n, W, u, w, m, cnt, dp[MAXN], w1[MAXN], v[MAXN];//n:宝物个数, W:总共载重, u:宝物价值, w:宝物重量, m:宝物件数
int main()
{
	scanf("%d%d", &n, &W);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d%d%d", &u, &w, &m);
		for(int j = 1; j <= m; j++)
		{
			cnt++;
			v[cnt] = u;
			w1[cnt] = w;
		}	
	}
	for(int i = 1; i <= cnt; i++)
		for(int j = W; j >= w1[i]; j--)
			dp[j] = max(dp[j], dp[j - w1[i]] + v[i]);
	printf("%d", dp[W]);
	return 0;
}