有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式:

第一行两个整数，N，V， (0<N≤1000(0<𝑁≤1000, 0<V≤20000)0<𝑉≤20000)，用空格隔开，分别表示物品种数和背包容积。

接下来有 N𝑁 行，每行三个整数 vi,wi,si𝑣𝑖,𝑤𝑖,𝑠𝑖，用空格隔开，分别表示第 i𝑖 种物品的体积、价值和数量。

输出格式:

输出一个整数，表示最大价值。

思路就是先构造一个dp数组，从dp[容量]往前推，不断重复dp[i]=max(dp[i],dp[i-当前体积]+当前价值)。

注意构造dp数组的时候是V+1,因为容量包含0也包含了V。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


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


vector<int> volume(N), value(N), count(N);
for (int i = 0; i < N; i++) {
cin >> volume[i] >> value[i] >> count[i];
}
 
//构造dp数组
vector<int> dp(V + 1, 0);


for (int i = 0; i < N; i++) {
int v = volume[i];
int w = value[i];
int n = count[i];


for (int j = V; j >= 0; j--) {
for (int k = 1; k <= n && k * v <= j; k++) {
dp[j] = max(dp[j], dp[j - k * v] + k * w);
}
}
}
cout << dp[V] << endl;
return 0;
}