平邑网站优化,鹤壁网站seo,网站推广目标关键词,wordpress右边微信有 N#xfffd; 种物品和一个容量是 V#xfffd; 的背包。
第 i#xfffd; 种物品最多有 si#xfffd;#xfffd; 件#xff0c;每件体积是 vi#xfffd;#xfffd;#xff0c;价值是 wi#xfffd;#xfffd;。
求解将哪些物品装入背包#xff0c;可使物…有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式
第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si,,用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤1000,≤100 0vi,wi,si≤1000,,≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例
10
原题链接
传送门
代码
#includebits/stdc.h
using namespace std;
//所以多重背包问题就是限制一件物品的可以装的数量
int f[110];
int main()
{int n,m;scanf(%d%d,n,m);for(int i0;in;i){int v,w,s;scanf(%d%d%d,v,w,s);for(int jm;jv;j--){for(int k1;ksk*vj;k){f[j]max(f[j],f[j-k*v]k*w);}}}printf(%d\n,f[m]);return 0;
}
总结
1.01背包是选择一件物品或者不选完全背包是一件物品可以选择无数件多重背包是一件物品可以选择若干件有一定的限制
2.第一个循环是遍历所有物品
3.第二个循环是从大到小遍历背包容量01背包和多重背包的第二层循环都是从大到小遍历背包体积完全背包是从小到大遍历背包体积
4.第三个循环是考虑一件物品选多少个可以选择0123……s件相同的物品小优化是一旦k*vj表示超出背包容量就跳出循环
5.最后我们要求的最大价值就是f[m]
