08背包初探.pptx

1、ACM程序设计,8. 背包初探,2020/7/12,1,Bone Collector,HDOJ 2602 大意 一个容量为V的袋子，N个骨头，每个有价值和容量，计算你能装的骨头的最大价值和。(N = 1000 , V = 1000 ),2020/7/12,2,思路,暴力？ O(2n) 贪心？ 无法得到全局最优解 DP？ 状态怎么表示？ 状态转移是什么？ 初始条件是什么？,2020/7/12,3,经典问题（1） 01背包,有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。 特点是每种物品仅有一件，可以选择放或不放。,2020

2、/7/12,4,定义状态：Fiv表示前i件物品放入一个容量为v的背包可以获得的最大价值。 则其状态转移方程便是：,2020/7/12,5,“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前i -1件物品相关的问题。 如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为Fi-1v； 如果放第i件物品，那么问题就转化为“前i -1件物品放入剩下的容量为v-Ci的背包中”，此时能获得的最大价值就是Fi-1v-Ci,再加上通过放入第i件物品获得的价值Wi。,2020/7/12,6,2020/7/12,7,#de

3、fine V 1111 #define N 1111 #define MAX(x,y) (x)(y)?(x):(y) int dpNV; int cN; int wN; void solve(int n,int v) int i,j; memset(dp,0,sizeof(int)*(v+1); for(i=0;in;i+) for(j=0;jci;j+) dpi+1j = dpij; for(j=ci;j=v;j+) dpi+1j = MAX(dpij,dpij-ci+wi); ,时间复杂度O(NV) 空间复杂度O(NV),空间复杂度的优化,空间复杂度却可以优化到O(V) 数组fV，能不能保

4、证第i次循环结束后fv中表示Fiv呢？ Fiv是由Fi-1v和Fi-1v-Ci两个子问题递推而来，能否保证在计算Fiv时（也即在第i次主循环中计算fv时）能够取用Fi-1v和Fi-1v-Ci的值呢？ 每次主循环中我们以v = V.0的递减顺序计算Fv，这样第i次循环时，在计算前，fv表示Fi-1v,fv-Ci保存的是Fi-1v-Ci的值。,2020/7/12,8,2020/7/12,9,#define V 1111 #define N 1111 #define MAX(x,y) (x)(y)?(x):(y) int dpV; int cN; int wN; void solve(int n,i

5、nt v) int i,j; memset(dp,0,sizeof(int)*(v+1); for(i=0;i=ci;j-) dpj = MAX(dpj,dpj-ci+wi); ,时间复杂度O(NV) 空间复杂度O(maxN,V),I NEED A OFFER!,HDU 1203 大意 N元钱，M个学校，每个学校的申请费为Ai,通过概率是Bi 求获得offer的最大概率,2020/7/12,10,思路,很明显一个01背包 变化在于状态转移 Fiv表示前i个学校，花v元钱申请的最大通过率 Fiv = maxFi-1v, Wi+(1-Wi)Fi-1v-Ci F00.V = 0 同样可以使用前面的技

6、巧，降低空间复杂度,2020/7/12,11,2020/7/12,12,#define V 11111 #define N 1111 #define MAX(x,y) (x)(y)?(x):(y) double dpV; int cN; double wN; void solve(int n,int v) int i,j; memset(dp,0,sizeof(double)*(v+1); for(i=0;i=ci;j-) dpj = MAX(dpj,wi+(1.0-wi)*dpj-ci); ,两种问法,要求“恰好装满背包”时的最优解 要求必须把背包装满 区别这两种问法的实现方法是在初始化的时

7、候有所不同。 要求恰好装满背包，那么在初始化时除了F0为0，其它F1.V均设为-INF，这样就可以保证最终得到的FV是一种恰好装满背包的最优解。 没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将F0.V全部设为0。,2020/7/12,13,初始化的F数组事实上就是在没有任何物品可以放入背包时的合法状态。 如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为-了。 如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全

8、部为0了。,2020/7/12,14,Piggy Bank,POJ 1384 存钱罐容量V为F-E，有n种硬币，每种硬币的价值为Wi，容量为Ci。问组成的硬币的最小价值和。 V=10000,n=500,Wi=50000,Ci=10000,2020/7/12,15,完全背包问题,有N种物品和一个容量为V的背包，每种物品都有无限件可用。放入第i种物品的耗费的空间是Ci，得到的价值是Wi。 求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。,2020/7/12,16,基本思路,这个问题非常类似于01背包问题，所不同的是每种物品有无限件。 从每种物品的角度考虑，与它

9、相关的策略已并非取或不取两种，而是有取0件、取1件、取2件直至取V/Ci件等很多种。,2020/7/12,17,如果仍然按照解01背包时的思路，令Fiv表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样： 求解状态Fi,v的时间是O(V/Ci) 总的时间复杂度为,2020/7/12,18,简单的优化,若两件物品i、j满足Ci=Wj，则将可以将物品j直接去掉，不用考虑。 优化操作的时间复杂度O(NlogN) 首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化,2020

10、/7/12,19,转化为01背包问题求解,最简单的想法是，考虑到第i种物品最多选V/Ci件，于是可以把第i种物品转化为V/Ci件费用及价值均不变的物品，然后求解这个01背包问题。 时间复杂度没有变化 二进制优化 把第i种物品拆成费用为Ci*2k、价值为Wi*2k的若干件物品，其中k取遍满足Ci*2k =V 的非负整数。 时间复杂度,2020/7/12,20,TLE,void solve(int n,int v) int i,j,ck,wk; dp0 = 0; for(i=1;i=ck;j-) dpj = MIN(dpj,dpj-ck+wk); ,2020/7/12,21,AC,void sol

11、ve(int n,int v) int i,j,ck,wk; dp0 = 0; for(i=1;i=ck;j-) dpj = MIN(dpj,dpj-ck+wk); ,2020/7/12,22,悼念512汶川大地震遇难同胞珍惜现在，感恩生活,HDU 2191 n元钱，m种大米，每种大米每袋单价pi，重量hi，总数ci 求最多买多少大米 n=100,m=100,pi=20,hi=200,ci=20,2020/7/12,23,经典问题（3）多重背包,有N种物品和一个容量为V的背包。 第i种物品最多有Mi件可用，每件耗费的空间是Ci，价值是Wi。 求解将哪些物品装入背包可使这些物品的耗费的空间总和不

12、超过背包容量，且价值总和最大。,2020/7/12,24,这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可。,2020/7/12,25,转化为01背包问题,把第i种物品换成Mi件01背包中的物品，则得到了物品数为sum(Mi)的01背包问题。 二进制优化 将第i种物品分成若干件01背包中的物品，其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数 令这些系数分别为1,2,22 ,2k-1;Mi-2k + 1，且k是满足Mi-2k + 1 0的最大整数。 M=13,分成1,2,4,6,2020/7/12,26,2020/7/12,27,void

13、solve(int n,int v) int i,j,ck,wk,k,mk; for(i=0;i0;k=ck;j-) dpj = MAX(dpj,dpj-ck+wk); ,更多的变形,推荐看背包九讲 本slides大量参考背包九讲，在此鸣谢其作者崔添翼,2020/7/12,28,课后作业,HDU WEB-DIY 5012 2013 湘潭大学 ACM程序设计作业8 开始时间2013-06-08 14:00:00 结束时间2013-06-29 14:00:00 密码：xtuacm2013,29,2013年暑假集训队选拔,1. 入队标准A. 2012年获得Regional铜奖或以上成绩队员B. Codeforces的第三高Rating为1600分以上队员C. 通过2+1选拔赛的队员 2. 队伍人数30人,2020/7/12,30,报名表格见群邮件，填好发送到 ,2013年暑假集训队选拔,3. 2+1选拔赛地点为工科楼6楼计算机系机房,个人赛场次 时间 1 2013-7-7 上午9点12点 2 2013-7-7 下午3点