一种物品拆成多个不同物品,就变成了01背包问题
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int N, V;
cin >> N >> V;
vector<int> dp(10010, 0), w, v;
while(N--) {
int ww, vv, t;
cin >> ww >> vv >> t;
while(t--) w.push_back(ww), v.push_back(vv);
}
for(int i = 0; i < w.size(); ++i)
for(int j = V; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[V] << endl;
return 0;
}