信息学奥赛一本通1268：【例9.12】完全背包问题代码+详解

2024-01-08 15:33:41

题目链接：1268

题目

1268：【例9.12】完全背包问题


时间限制: 1000 ms ??? ??? 内存限制: 65536 KB
提交数: 40600 ??? 通过数: 21799

【题目描述】

设有n�种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M�，今从n�种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M�，而价值的和为最大。

【输入】

第一行：两个整数，M�(背包容量，M≤200�≤200)和N�(物品数量，N≤30�≤30)；

第2..N+12..w[i]+1行：每行二个整数Wi,Ci,表示每个物品的重量和价值。

【输出】

仅一行，一个数，表示最大总价值。

【输入样例】

10 4
2 1
3 3
4 5
7 9

【输出样例】

max=12

题目详细解析

? ? ? ? 了解背包问题

? ? ? ? 01背包，只能背一次，后面不能在背了

? ? ? ? 多重背包，可以背w[i]次

? ? ? ? 完全背包，可以背无限次。

? ? ? ? 来，我们先按多重背包的思想来做

? ? ? ? 比如f[5](多重背包的j是逆序判断的)

f[5]=max(f[5],f[3]+x[i]);

等等，你们有没有发现问题？

f[3]还没有被刷新就用上了，那么，该怎么办呢？

就要按顺序来判断了。

for(int j=1;j<=w[i];j++)

完全背包跟踪：

i=0,f[0],....f[5]=0;前0个人--价值=0?

i=1,前1个人,?????j=w[1]..<=c=5;!!只有01背包??

????j=2,f[2]=max(f[2]=0,f[2-w[1]]+v[1]=100,

????j=3,f[3]=max(f[3]=0,f[3-w[1]]+v[1]=f[1]+v[1]=100

????j=4,f[4]=max(f[4]=0,f[4-w[1]]+v[1]=f[4-2]+100=f[2]+100??!!重要

//j=4时，f[4]用到的f[2]是本行的f[2]=100,f[4]=100+100=200;?

//!!假设，j从大到小，那么j=4时,f[4]=f[2]+100,f[2]是上一行=0,f[4]=100错误?

????j=5;f[5]=max(f[5],f[5-w[1]]+v[1]=f[3]+100=200;

结果：i=1,f[0]=0;f[1]=0,f[2]=100,f[3]=100,f[4]=200,f[5]=200,

i=2,前2个人?j=w[2]=3..<=c=5;

??f[3]=max(f[3]=100,f[3-w[2]]+v[2]=f[0]+120=120)=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]+120=100+120=220=220?

代码（有注释）

?
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,c;
int w[1001],v[1001];
int f[50001];
int main()
{  int i,j;
cin>>n>>c;
for(i=1;i<=n;i++)
cin>>w[i];
for(i=1;i<=n;i++)
cin>>v[i];
for(i=1;i<=n;i++)//物品
for(j=w[i];j<=c;j++)//!!只有完全背包，是从小 到大
f[j]=max(f[j],f[j-w[i]]+v[i]);
cout<<f[c];
return 0;
}

 }

?

不点赞关注收藏的暑假作业翻倍！


?

文章来源:https://blog.csdn.net/grkgrkhnhcgchxjs/article/details/135406733
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。