第九章动态规划.ppt
《第九章动态规划.ppt》由会员分享,可在线阅读,更多相关《第九章动态规划.ppt(38页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第九章 动态规划,第三节 背包问题,第三节 背包问题,一、01背包问题问题: 有N件物品和一个容量为V的背包。第i件物品的费用(即体积,下同)是wi,价值是ci。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 基本思路:这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。用子问题定义状态:即fiv表示前i件物品(部分或全部)恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:fiv=maxfi-1v,fi-1v-wi+ci。这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放
2、入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”;如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-wi的背包中”,此时能获得的最大价值就是f i-1v-wi再加上通过放入第i件物品获得的价值ci。,注意fiv有意义当且仅当存在一个前i件物品的子集,其费用总和为v。所以按照这个方程递推完毕后,最终的答案并不一定是fNV,而是fN0.V的最大值。如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项fi-1v,这样就可以保证fN
3、V就是最后的答案。但是若将所有fij的初始值都赋为0,你会发现fnv也会是最后的答案。为什么呢?因为这样你默认了最开始fij是有意义的,只是价值为0,就看作是无物品放的背包价值都为0,所以对最终价值无影响,这样初始化后的状态表示就可以把“恰”字去掉。,优化空间复杂度 以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1.N,每次算出来二维数组fi0.V的所有值。那么,如果只用一个数组f 0.V,能不能保证第i次循环结束后fv中表示的就是我们定义的状态fiv呢?fiv是由fi-1
4、v和fi-1v-wi两个子问题递推而来,能否保证在推fiv时(也即在第i次主循环中推fv时)能够得到fi-1v和fi-1v-wi的值呢?事实上,这要求在每次主循环中我们以v=V.0的逆序推fv,这样才能保证推fv时fv-wi保存的是状态fi-1v-wi的值。伪代码如下:for i=1.N for v=V.0 fv=maxfv,fv-wi+ci; 其中fv=maxfv,fv-wi+ci相当于转移方程fiv=maxfi-1v,fi-1v-wi+ci,因为现在的fv-wi就相当于原来的fi-1v-wi。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了fiv由fiv-wi推知,与本题意不符,但它
5、却是另一个重要的完全背包问题最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。,【例1】 0/1背包【问题描述】 一个旅行者有一个最多能用m公斤的背包,现在有n件物品,它们的重量分别是W1,W2,.,Wn,它们的价值分别为C1,C2,.,Cn.若每种物品只有一件求旅行者能获得最大总价值。 【输入格式】 第一行:两个整数,M(背包容量,M=200)和N(物品数量,Ny?x:y; /求x和y最大值int main() scanf(%d%d,使用二维数组存储各子问题时方便,但当maxm较大时,如maxm=2000时不能定义二维数组f,怎么办,其实可以用一维数组。,【解法二】本问题的数学
6、模型如下:设 fv表示重量不超过v公斤的最大价值, 则fv=maxfv,fv-wi+ci,当v=wi,1using namespace std;const int maxm = 2001, maxn = 31;int m, n;int wmaxn, cmaxn;int fmaxm; int main() scanf(%d%d,总结:01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。,二、完全背包问题问题:有N种物品和一个
7、容量为V的背包,每种物品都有无限件可用。第i种物品的费用是wi,价值是ci。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。,基本思路:这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件等很多种。如果仍然按照解01背包时的思路,令fiv表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:fiv=maxfi-1v-k*wi+k*ci|0=k*wi= v。将01背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说
8、明01背包问题的方程的确是很重要,可以推及其它类型的背包问题。这个算法使用一维数组,先看伪代码:for i=1.N for v=0.V fv=maxfv,fv-wi+ci; 你会发现,这个伪代码与01背包问题的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢?首先想想为什么01背包问题中要按照v=V.0的逆序来循环。这是因为要保证第i次循环中的状态fiv是由状态fi-1v-wi递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果fi-1v-wi。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一
9、件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果fiv-wi,所以就可以并且必须采用v= 0.V的顺序循环。这就是这个简单的程序为何成立的道理。这个算法也可以以另外的思路得出。例如,基本思路中的状态转移方程可以等价地变形成这种形式:fiv=maxfi-1v,fiv-wi+ci,将这个方程用一维数组实现,便得到了上面的伪代码。,【例9-12】、完全背包问题【问题描述】设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M,而价值的和为最大。【输入格式】第一行
10、:两个整数,M(背包容量,M=200)和N(物品数量,N=wi ,1using namespace std;const int maxm=2001,maxn=31;int n,m,v,i;int cmaxn,wmaxn;int fmaxm;int main() scanf(%d%d,一个简单有效的优化 完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足wi=cj,则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高的j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的
11、复杂度,因为有可能特别设计的数据可以一件物品也去不掉。转化为01背包问题求解 既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/wi件,于是可以把第i种物品转化为V/wi件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。更高效的转化方法是:把第i种物品拆成费用为wi*2k、价值为ci*2k的若干件物品,其中k满足wi*2kV。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个
12、2k件物品的和。这样把每种物品拆成O(log(V/wi)+1)件物品,是一个很大的改进。总结 完全背包问题也是一个相当基础的背包问题,它有两个状态转移方程,分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会,不仅记住,也要弄明白它们是怎么得出来的,最好能够自己想一种得到这些方程的方法。事实上,对每一道动态规划题目都思考其方程的意义以及如何得来,是加深对动态规划的理解、提高动态规划功力的好方法。,三、多重背包问题有N种物品和一个容量为V的背包。第i种物品最多有ni件可用,每件费用是wi,价值是ci。求解将哪些物品装入背包可使这些物品的费用总和不超过
13、背包容量,且价值总和最大。,基本算法: 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有ni+1种策略:取0件,取1件取ni件。令fiv表示前i种物品恰放入一个容量为v的背包的最大权值,则:fiv=maxfi-1v-k*wi+ k*ci|00的最大整数(注意:这些系数已经可以组合出1ni内的所有数字)。例如,如果ni为13,就将这种物品分成系数分别为1,2,4,6的四件物品。 分成的这几件物品的系数和为ni,表明不可能取多于ni件的第i种物品。另外这种方法也能保证对于0.ni间的每一个整数,均可以用若干个系数的和表示,这个证明可以分0.2k-1和
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九 章动 规划
限制150内