(HDUACM201303版_07)背包专题

ACM程序设计杭州电子科技大学刘春英[e-mail]2020/1/152课后作业，你了吗？2020/1/153每周一星（6）：ray007great2020/1/154第七讲背包算法（KnapsackAlgorithm）2020/1/155导引问题-食堂就餐现有餐券1张，面值10元菜肴N种（价格精确到0.1元）：炸鸡腿3元；大排1.5元；荷包蛋：1元；炒青菜：1.2元；番茄炒蛋：2.5元......餐券的特点：一次性使用，不找零；问：若每种菜只挑一个，为了充分发挥餐券的作用，最多可以消费多少元？2020/1/156什么是背包问题背包的基本模型：给你一个容量为V的背包和若干种物品，在一定的限制条件下（每种物品都占用一定容量），问最多能放进多少价值的物品？2020/1/157关于背包问题1、最典型、最基本的DP问题；2、理解并熟练掌握背包问题意义重大；3、DP问题中“状态”概念的理解；4、背包的每个容量就是“状态”,选择每个物品就是“状态的决策”；2020/1/158背包问题的分类01背包完全背包多重背包混合三种背包二维费用背包分组背包有依赖的背包2020/1/15901背包问题:最基础的背包问题：有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]}一、01背包2020/1/1510SampleInput15101234554321SampleOutput14一、01背包-BoneCollector2020/1/1511一、01背包-BoneCollector(V,C)012345678910000000000000(1,5)00000111111(2,4)00002222233(3,3)00033335555(4,2)00447777799(5,1)0559991212121214问题分解：当前最优解，要么包含第i种物品，要么不包含第i种物品DP[i][j]表示前i个物品,背包容量为j的最优值。状态转移方程为：DP[i][j]=max(DP[i-1][j],DP[i-1][j-v[i]]+w[i])2020/1/1512时间复杂度N*V,空间复杂度N*V空间复杂度优化:只用一位数组DP[j]来实现；但此时，遍历背包的顺序必须反一反,想想为什么?01背包问题伪代码如下:fori=1ton//所有物品forj=Vtov[i]dp[j]=max(dp[j],dp[j-v[i]]+w[i]);空间优化到一维V原因：如果顺序遍历,一种物品会被取好多次一、01背包-BoneCollector2020/1/1513二、完全背包Piggy-Bank完全背包特点:一种物品可以取无数个可否转化成01背包问题？朴素的转化方式是？回忆01背包为何要对容量按照逆序循环？和01背包类似,不过就是正着写！这类能不能达到的问题应该怎么实现?2020/1/1514三、多重背包珍惜现在，感恩生活多重背包特点:一种物品有C个（既不是固定的1个，也不是无数个）最朴素的想法?优化的方法：运用神奇的二进制,进行物品拆分,转化成01背包物品拆分,把13个相同的物品分成4组(1,2,4,6)用这4组可以组成任意一个1~13之间的数!原理:一个数总可以用2^k表示而且总和等于13,所以不会组成超过13的数所以可将一种有C个的物品拆分成1,2,4,...,2^(k-1),C-(2^k-1)然后进行01背包2020/1/1515优化部分的参考代码intt=1;while(x=t){v[cnt]=a*t;c[cnt++]=b*t;x-=t;t=1;}if(x){v[cnt]=a*x;c[cnt++]=b*x;}2020/1/1516四、混合三种背包混合背包特点:如果将三种背包问题混合起来，也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包），应该怎么求解呢？fori=1..Nif第i件物品属于01背包ZeroOnePack(c[i],w[i])elseif第i件物品属于完全背包CompletePack(c[i],w[i])elseif第i件物品属于多重背包MultiplePack(c[i],w[i],n[i])详见：背包问题九讲2020/1/1517五、二维费用背包二维费用背包问题:对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量），求怎样选择物品可以得到最大的价值。设第i件物品所需的两种代价分别为a[i]和b[i]，两种代价可付出的最大值（两种背包容量）分别为V和U，物品的价值为w[i]。对应算法：费用加了一维，只需状态也加一维即可！设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值，状态转移方程则为：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}详见：背包问题九讲2020/1/1518六、分组背包分组背包问题:N件物品和一个容量为V的背包，第i件物品的费用是c[i]，价值是w[i]。这些物品被分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使物品的费用总和不超过背包容量，且价值总和最大。对应算法：问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}使用一维数组的伪代码如下：for所有的组kforv=V..0for所有的i属于组kf[v]=max{f[v],f[v-c[i]]+w[i]}2020/1/1519附录：01背包参考代码（2602）#includeiostream#includecstringusingnamespacestd;intdp[1001],v[1000],p[1000];inlineintmax(inta,intb){returnab?a:b;}intmain(){intc;scanf(%d,&c);while(c--){intn,V,i,j;scanf(%d%d,&n,&V);for(i=0;in;i++)scanf(%d,&p[i]);for(i=0;in;i++)scanf(%d,&v[i]);memset(dp,0,sizeof(dp));for(i=0;in;i++)for(j=V;j=v[i];j--)dp[j]=max(dp[j],dp[j-v[i]]+p[i]);printf(%d\n,dp[V]);}}2020/1/1520鸣谢：本讲内容参考自cuitianyi（zju_DD）总结的“背包问题九讲”，在此表示感谢！若想了解更多关于背包问题的算法，可以直接搜索该资料即可。2020/1/1521WelcometoHDOJThankYou~