题目
有N件物品和一个容量为V的背包。第i件物品的体积是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
这时候我们可以用二维数组进行做了
//二维数组实现背包
#include<stdio.h>
#include<string.h>
#defineN1002
intmax[N][N];
intmain()
{
intjiazhi[N],tiji[N],t,i,j,n,v;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&v);
for(i=1;i<=n;i++)
scanf("%d",&jiazhi[i]);
for(i=1;i<=n;i++)
scanf("%d",&tiji[i]);
memset(max,0,sizeof(max));
for(i=1;i<=n;i++)
for(j=0;j<=v;j++)
{
if(tiji[i]<=j&&max[i-1][j]<max[i-1][j-tiji[i]]+jiazhi[i])
max[i][j]=max[i-1][j-tiji[i]]+jiazhi[i];
else
max[i][j]=max[i-1][j];
}
printf("%d\n",max[n][v]);
}
return0;
}
|
但是我们为了以后解决更加复杂的背包必须学会用一维数组解决它
先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。
伪代码如下:
fori=1..N
forv=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
画个图给大家演示下
也就是说此时的f[v],f[v-c[i]]是前面的
假设体积是10
背包体积----->>>>>
价值
|
大小
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
|
|
|
|
|
|
2
|
1
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
2
|
放
|
第
|
一
|
个
|
物
|
品
|
|
1
|
2
|
2
|
2
|
3
|
3
|
3
|
3
|
3
|
3
|
3
|
3
|
放
|
第
|
二
|
个
|
|
|
|
5
|
3
|
2
|
2
|
3
|
3
|
3
|
8
|
8
|
8
|
8
|
8
|
|
|
|
|
|
|
|
4
|
4
|
2
|
2
|
3
|
3
|
3
|
8
|
8
|
8
|
8
|
12
|
|
|
|
|
|
|
|
3
|
5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
可以看出f[v]=max{f[v],f[v-c[i]]+w[i]};
V是从大到小的
其中的f[v],f[v-c[i]]是前面的值比较的结果赋值给f[v]
比如说当i=5的时候f[v]>f[v-5]注意两者都是i=4时候的值得出的结果12赋值到新的f[v]但是此时的f[v]是i=5的
当把最后一行改写成556的时候我们可以看出f[v-6]=f[4]+55大于f[v]所以我们可以得出新的f[v]=f[4]+55这样结果就是取的体积为126
代码如下//一维数组实现背包问题
#include<stdio.h>
#include<string.h>
#defineN1002
intmain()
{
intdp[N],vol[N],val[N];
intt,n,i,j,v;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&v);
for(i=1;i<=n;i++)
scanf("%d",&val[i]);
for(i=1;i<=n;i++)
scanf("%d",&vol[i]);
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=v;j>=vol[i];j--)
if(dp[j]<dp[j-vol[i]]+val[i])
dp[j]=dp[j-vol[i]]+val[i];
printf("%d\n",dp[v]);
}
return0;
}
初始化的细节问题
我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。
为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。
这个小技巧完全可以推广到其它类型的背包问题,后面也就不再对进行状态转移之前的初始化进行讲解。
分享到:
相关推荐
创建用户(以system用户登录) --创建用户,指定表空间 --PS:导入的dmp数据库文件的表空间一定要与导出的数据库的表空间一致 --所以这里要指定用户的表空间为hnust_data create user hnust_prd2 identified by ...
ssm的例子 自己做的,很多还不完善,!!!!!!
hnust操作系统课程设计
hnust的计算机组成原理的课程设计,五个实验的源码加上实验报告都在压缩包里,希望能帮到学弟学妹们(五个实验分别是 ROM仿真、验证74LS181、运算器、跑马灯、模拟微程序实现指令)
湖南科技大学2022年编译原理知识点总结,自己手敲的。
湖南科技大学大二下学期的数据通信技术课程,光纤通信课本中老师画的重点总结文档
hnust大一下学期数据结构课设的报告和源代码(放在了附录里面)
hnust计组课设要用到的东西都在里面了
人工智能,第一次作业,遗传算法,旅行者问题,用Python写出来,包括结果图片。Hnust.
hnust 软件测试报告+代码
湖南科技大学大二下学期先后开展java web和数据库课程设计,两个课设项目可以通用,老师一般会允许自拟选题,所以在此统一打包,以供参考。内含两个课设的报告、源代码、流程图文件(可修改)、课设指导书,并附赠...
湖南科技大学 2022年大二下学期数据库期中考试复习笔记,自己手码的。
花了三天时间搞出来的人事管理系统的源码,现在把它放出来,其实大部分的时间都花在GUI上了,用的是python3,给需要的学弟学妹们参考参考
2023湖科大hnust计算机学院综合创新实训3课程设计报告,(软件工程),人事管理系统的实现,湖南科技大学
大二上的eda考查课的实验,额外实现了停车等待2分钟后收费1元/min。内含项目文件(实测可运行),代码,报告,视频和照片,不足之处在于时间略有偏差
题目十九:复印机逻辑控制电路设计★ 1)用按键输入复印的次数,用三个数码管显示,最大555,初始为0;(使用六个按键表示0-5数字键); 2)用另外...
自己写的,仅供参考哦
老师给的,考试的题都从里面出
软工真题,只有一年的,22-23的题和这个几乎一样