手机网站触屏版,淘宝官网首页手机版,网站开发实训安排,网站建设培训多少钱题目链接#xff1a;1268
题目
1268#xff1a;【例9.12】完全背包问题 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 40600 通过数: 21799
【题目描述】 设有n#xfffd;种物品#xff0c;每种物品有一个重量及一个价值。但每种物品的数量是无限的…
题目链接1268
题目
1268【例9.12】完全背包问题 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 40600 通过数: 21799
【题目描述】 设有n种物品每种物品有一个重量及一个价值。但每种物品的数量是无限的同时有一个背包最大载重量为M今从n种物品中选取若干件(同一种物品可以多次选取)使其重量的和小于等于M而价值的和为最大。 【输入】 第一行两个整数M(背包容量M≤200≤200)和N(物品数量N≤30≤30) 第2..N12..w[i]1行每行二个整数Wi,Ci,表示每个物品的重量和价值。 【输出】 仅一行一个数表示最大总价值。 【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
max12
题目详细解析 了解背包问题 01背包只能背一次后面不能在背了 多重背包可以背w[i]次 完全背包可以背无限次。 来我们先按多重背包的思想来做 比如f[5](多重背包的j是逆序判断的)
f[5]max(f[5],f[3]x[i]);
等等你们有没有发现问题
f[3]还没有被刷新就用上了那么该怎么办呢
就要按顺序来判断了。
for(int j1;jw[i];j) 完全背包跟踪 i0,f[0],....f[5]0;前0个人--价值0 i1,前1个人, jw[1]..c5;!!只有01背包 j2,f[2]max(f[2]0,f[2-w[1]]v[1]100, j3,f[3]max(f[3]0,f[3-w[1]]v[1]f[1]v[1]100 j4,f[4]max(f[4]0,f[4-w[1]]v[1]f[4-2]100f[2]100 !!重要 //j4时f[4]用到的f[2]是本行的f[2]100,f[4]100100200; //!!假设j从大到小那么j4时,f[4]f[2]100,f[2]是上一行0,f[4]100错误 j5;f[5]max(f[5],f[5-w[1]]v[1]f[3]100200; 结果i1,f[0]0;f[1]0,f[2]100,f[3]100,f[4]200,f[5]200, i2,前2个人 jw[2]3..c5; f[3]max(f[3]100,f[3-w[2]]v[2]f[0]120120)120; f[4]max(f[4]200,f[4-w[2]]v[2]f[1]120 120 f[5]max(f[5]200,f[5-w[2]]v[2]f[2]120100120220220 代码有注释
#includebits/stdc.h
using namespace std;
int main()
{int n,c;
int w[1001],v[1001];
int f[50001];
int main()
{ int i,j;
cinnc;
for(i1;in;i)
cinw[i];
for(i1;in;i)
cinv[i];
for(i1;in;i)//物品
for(jw[i];jc;j)//!!只有完全背包是从小 到大
f[j]max(f[j],f[j-w[i]]v[i]);
coutf[c];
return 0;
}} 不点赞关注收藏的暑假作业翻倍
