有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
* 第一类物品只能用1次（01背包）；
* 第二类物品可以用无限次（完全背包）；
* 第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
* si=−1 表示第 i 种物品只能用1次；
* si=0 表示第 i 种物品可以用无限次；
* si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例
8
1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 const int array_size = 1001; 6 int f[array_size], N, V, v, w, s; 7 struct goods { 8 int v, w, s; 9 }; 10 vector<goods> vessel; 11 int main() { 12 cin >> N >> V; 13 for (int i = 0; i < N; ++i) { 14 cin >> v >> w >> s; 15 if(s<=0) 16 vessel.push_back(goods{ v,w,s }); //push进去01背包问题和完全背包问题的物品 17 else { 18 for (int k = 1; k <= s; k *= 2) {//将多重背包问题转为01背包问题然后push进去 19 s -= k; 20 vessel.push_back(goods{ k * v, k * w, -1 }); 21 } 22 if (s > 0) 23 vessel.push_back(goods{ s * v,s * w,-1 }); 24 } 25 } 26 for (goods g : vessel) { 27 if (g.s == -1) //01背包问题 28 for (int i = V; i >= g.v; --i) 29 f[i] = max(f[i], f[i - g.v] + g.w); 30 else //完全背包问题 31 for (int i = g.v; i <= V; ++i) 32 f[i] = max(f[i], f[i - g.v] + g.w); 33 } 34 cout << f[V]; 35 }