第21讲-动态规划(背包问题)

1、ACM-ICPC培训培训投资分配问题背包问题ACM算法设计与分析王建芳ACM-ICPC培训培训投资分配问题河南理工大学ACM-ICPC培训 现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元）；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题：如何确定各工厂的资金数，使得总的利润为最大。 nixaxxgziniiniii.2.1 0)( max11据此，有下式：河南理工大学ACM-ICPC培训 令：fk(x) 表示以数量为x 的资金分配给前k 个工厂，所得到的最大利润值。 用动态规划求解，就是求 fn(a) 的问

2、题。 当 k=1 时， f1(x) = g1(x) （因为只给一个工厂） 当1kn 时，其递推关系如下： 设：y 为分给第k 个工厂的资金（其中 0y x ），此时还剩 x y（万元）的资金需要分配给前 k1 个工厂,如果采取最优策略，则得到的最大利润为fk1(xy) ,因此总的利润为： gk(y) fk1(xy) 投资分配问题河南理工大学ACM-ICPC培训 nkyxfygxfkkxyk.)()(max)(3210 其中 如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，x。上式可变为： )()(max)(,yxfygxfkkxyk 1210所以，根据动态规划的最优化原理，

3、有下式：投资分配问题河南理工大学ACM-ICPC培训设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。依据题意，是要求 f4(60) 。投资分配问题河南理工大学ACM-ICPC培训按顺序解法计算。第一阶段：求 f1(x)。显然有 f1(x) g1(x)，得到下表第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。 )60()(max)60(1260,10,02yfygfy 投资分配问题河南理工大学ACM-ICPC培训12006520605055655080408520850max)0()60()

4、10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最优策略为（40，20），此时最大利润为120万元。同理可求得其它 f2(x) 的值。 )60()(max)60(1260,10,02yfygfy 投资分配问题河南理工大学ACM-ICPC培训2210 ,10 ,50212121212121(50)m ax()(50) (0)(50)(10)(40)(20)(30) 105(30)(20)(40)(10)(50)(0)yfgyfygfgfgfgfgfgf最优策略为（最优策略为（3030，202

5、0），此时最大利润为），此时最大利润为105105万元。万元。投资分配问题河南理工大学ACM-ICPC培训2210 ,10 ,40(40)m ax()(40)90yfgyfy最优策略为（20，20），此时最大利润为90万元。2210 ,10 ,20 ,30(30)m ax()(30)70yfgyfy最优策略为（20，10），此时最大利润为70万元。投资分配问题河南理工大学ACM-ICPC培训2210 ,10 ,20(20)m ax()(20) 50yfgyfy2210 ,10 ,(10)m ax()(10)20yfgyfy最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。

6、 f2(0) 0。最优策略为（0，0），最大利润为0万元。 得到下表最优策略为（20，0），此时最大利润为50万元。投资分配问题河南理工大学ACM-ICPC培训第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。 )60()(max)60(2360,10,03yfygfy 投资分配问题河南理工大学ACM-ICPC培训1550115201105010070859060105251200max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max23232323232323 fgfgfgfgfg

7、fgfg最优策略为（最优策略为（20，10，30），最大利润为），最大利润为155万元。万元。同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表投资分配问题河南理工大学ACM-ICPC培训第四阶段：求 f4(60)。即问题的最优策略。)60()(max)60(3460,10,04yfygfy投资分配问题河南理工大学ACM-ICPC培训16007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最优

8、策略为（20，0，30，10），最大利润为160万元。投资分配问题ACM-ICPC培训培训背包问题河南理工大学ACM-ICPC培训 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a 公斤，公斤，设有设有n 种物品可供他选择装入包中。已知每种物品的重量及种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件） a1 a2 aj an每件使用价值每件

9、使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。河南理工大学ACM-ICPC培训o 从每种物品的角度考虑，与它相关的策略已并非从每种物品的角度考虑，与它相关的策略已并非取或不取取或不取 两种，而是有取两种，而是有取0件、取件、取1件、取件、取2件件等很多种。如果仍然按照解等很多种。如果仍然按照解01背包时的思背包时的思路，令路，令fiv表示前表示前i种物品恰放入一个容量为种物品恰放入一个容量为v的背包的最大权的背包的最大权 值。仍然可以按照每种物品不值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：同的策

10、略写出状态转移方程，像这样：ofiv=maxfi-1v-k*ci+k*wi|0=k*ci=wi 1=i=wi then m:=f(x-i)+ci;16 if mt then t:=m;17 end;18 f:=t;19 end;20end;2122begin23readln(m,n);24for i:= 1 to n do25 readln(wi,ci);26writeln(f(m);27end.河南理工大学ACM-ICPC培训o 当当m不大时不大时,可以通过可以通过,但当但当m较大时较大时,容易超时，容易超时，改进的递归法改进的递归法 o 改进的的递归法的思想还是以空间换时间改进的的递归法的

11、思想还是以空间换时间,这只这只要将递归函数计算过程中的各个子函数的值保存要将递归函数计算过程中的各个子函数的值保存起来起来,开辟一个一维数组即可开辟一个一维数组即可o 其实这种以空间换时间的存储式搜索就是动态规其实这种以空间换时间的存储式搜索就是动态规划的思想划的思想河南理工大学ACM-ICPC培训o 1program knapsack04; 2const maxm=2000;maxn=30; 3type ar=array0.maxn of integer; 4var m,n,j,i,t:integer; 5 c,w:ar; 6 p:array0.maxm of integer; 7funct

12、ion f(x:integer):integer; 8var i,t,m:integer; 9begin10 if px-1 then f:=px /标记是标记是否计算过避免重复计算（很重要）否计算过避免重复计算（很重要）11 else 12 begin1o14 begin15 t:=-1;16 for i:=1 to n do 3 v17 begin18 if x=wi then m:=f(i-wi)+ci;19 if mt then t:=m;20 end;21 px:=t;22 end;23 f:=px;24 end;25end;2627begin28 readln(m,n);29 fo

13、r i:= 1 to n do30 readln(wi,ci);31 fillchar(p,sizeof(p),-1); /搜索中用于存储各阶段的最优质32 writeln(f(m);33end.ACM-ICPC培训培训0-1背包问题河南理工大学ACM-ICPC培训给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?niiixv1maxnixCxwiniii1,1 , 010-1背包问题0-1背包问题是一个特殊的整数规划问题。河南理工大学ACM-ICPC培训o 有N件物品和一个容量为V的背包。第i件物品的费用是ci

14、，价值是wi。求解将哪些物品装入背包可使价值总和最大。o 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。河南理工大学ACM-ICPC培训o用子问题定义状态：即用子问题定义状态：即fiv表示表示前前i件物品恰放入件物品恰放入(不一定真的是每不一定真的是每个都放进去，而是指最有策略）个都放进去，而是指最有策略）一个容量为一个容量为v的背包可以获得的最大的背包可以获得的最大价值。则其状态转移方程便是：价值。则其状态转移方程便是：ofiv=maxfi-1v,fi-1v-ci+wio这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它这个方程非常重要，基本上所有跟背包相关的问题

15、的方程都是由它衍生出来的。所以有必要将它详细解释一下：衍生出来的。所以有必要将它详细解释一下：n“将前i件物品放入容量为v的背包中”这个子问题 若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。n如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为fi-1v；n如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-ci的背包中”，此时能获得的最大价值就是fi-1v-ci再加上通过放入第i件物品获得的价值wi。河南理工大学ACM-ICPC培训o 这个问题非常类似于这个问题非常类似于01背包问题，所不同的是每背包问题

16、，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取与它相关的策略已并非取或不取 两种，而是有两种，而是有取取0件、取件、取1件、取件、取2件件等很多种。如果仍然等很多种。如果仍然按照解按照解01背包时的思路，令背包时的思路，令fiv表示前表示前i种物品种物品恰放入一个容量为恰放入一个容量为v的背包的最大权的背包的最大权 值。仍然可值。仍然可以按照每种物品不同的策略写出状态转移方程，以按照每种物品不同的策略写出状态转移方程，像这样：像这样：ofiv=maxfi-1v-k*ci+k*wi|0=k*ci2n时，算法需要(

17、n2n)计算时间。 0-1背包问题河南理工大学ACM-ICPC培训01背包问题描述：一个旅行者有一个最多能用M公斤的背包，现在有N件物品，它们的重量分别是W1，W2，.,Wn,它们的价值分别为P1,P2,.,Pn.若每种物品只有一件求旅行者能获得最大总价值。河南理工大学ACM-ICPC培训方式一：遍历M*N的数组，对应下图包的总容量M20,物品种类数N5河南理工大学ACM-ICPC培训o代码如下：代码如下：oconst int nRes=5;/5种物品种物品oint nResWeightnRes+1=0,5,3,4,7,8;/每种物品对应重量每种物品对应重量oint nResValuenRes

18、+1=0,14,6,9,18,20;/每种物品对应价值每种物品对应价值oconst int nTotleW=20;/背包容量为背包容量为20oint nValueTablenRes+1nTotleW+1=0;/动态价值表，每一项对应包当前所能装入的最优值动态价值表，每一项对应包当前所能装入的最优值oint KitBag()oofor(int i=1;i=nRes;i+)ofor(int j=1;j=nResWeighti) /当包容量大于等于当前物品重时当包容量大于等于当前物品重时o/如果装入当前物品所能达最大价值如果装入当前物品所能达最大价值不装当前物品，包选装前面物品所能获得的最大价值不装

19、当前物品，包选装前面物品所能获得的最大价值o/装入当前物品所能达最大价值装入当前物品所能达最大价值=当前物品价值当前物品价值+当前包容量当前包容量j扣除当前物品重量后，剩余的容量所能装入的最大价值。扣除当前物品重量后，剩余的容量所能装入的最大价值。o/对照上表，当遍历到对照上表，当遍历到i=2,j=8时，时，nValueTablei-1j-nResWeighti=nValueTable15=14，满足条件就装入物品。，满足条件就装入物品。o if(nResValuei+nValueTablei-1j-nResWeightinValueTablei-1j)onValueTableij=nResV

20、aluei+nValueTablei-1j-nResWeighti;/当前物品装入包当前物品装入包.o else/当前物品不装入包，当前包容量下的最大价值仍然是原来的价值当前物品不装入包，当前包容量下的最大价值仍然是原来的价值onValueTableij=nValueTablei-1j;ooelse/包容量不足以装入当前物品时，沿用原来的包容量最大价值包容量不足以装入当前物品时，沿用原来的包容量最大价值onValueTableij=nValueTablei-1j;o ocout最大值为：最大值为：=nResWeightnR)/包容量大于等于当前物品重包容量大于等于当前物品重o/获得物品放入和不

21、放入两种情况中的价值最大者获得物品放入和不放入两种情况中的价值最大者nnValueTablenRnW=max(nResValuenR+RecursionBag(nR-1,nW-nResWeightnR),/物品物品入包后的价值入包后的价值nRecursionBag(nR-1,nW);/物品不入包的最大价值物品不入包的最大价值ooelse/包容量不足以放入当前物品包容量不足以放入当前物品nnValueTablenRnW=RecursionBag(nR-1,nW);oreturn nValueTablenRnW;o河南理工大学ACM-ICPC培训o 对比两种方式可知，第二种方式遍历的数据量为对比两

22、种方式可知，第二种方式遍历的数据量为黄色标注结点，要小于第一种方式的数据访问量。黄色标注结点，要小于第一种方式的数据访问量。河南理工大学ACM-ICPC培训o 0-1背包问题基本题型：n http:/ 二维费用的背包问题河南理工大学ACM-ICPC培训二维背包问题的条件可概括为下表 二维费用的背包问题河南理工大学ACM-ICPC培训二维背包问题可以归纳为如下形式的整数线性规划问题： maxc1x1+cixi+cnxn a1x1+aixi+anxna b1x1+bixi+bnxnb xi为非负整数，i=1，n正如一维背包问题那样，二维背包问题也可以用动态规划求解。 二维费用的背包问题河南理工大学

23、ACM-ICPC培训二维费用的背包问题o 问题问题o 二维费用的背包问题是指：对于每件物品，具有二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价的价值。设这两种代价分别为代价1和代价和代价2，第，第i件物品所需的两种代价分别为件物品所需的两种代价分别为ai和和bi。两种。两种代价可付出的最大值（两种背包容量）分别为代价可付

24、出的最大值（两种背包容量）分别为V和和U。物品的价值为。物品的价值为wi。河南理工大学ACM-ICPC培训算法思想o 费用加了一维，只需状态也加一维即可。设费用加了一维，只需状态也加一维即可。设fivu表示前表示前i件物品付出两种代价分别为件物品付出两种代价分别为v和和u时可获得的最大价值。状态转移方程就是：时可获得的最大价值。状态转移方程就是：n fivu=maxfi-1vu,fi-1v-aiu-bi+wi。河南理工大学ACM-ICPC培训码头有一艘载重量为30t，最大容为1210m3的船，由于运输需要,这艘船可用于装载四种货物到珠江口，它们的单位体积,重量及价值量见下表:现求如何装载这四种

25、货物使价值量最大。 河南理工大学ACM-ICPC培训背包问题小结（1）o 一、01背包o 最简单的背包，每件物品选或者不选。for(int i = 1; i = ci; -j) dpj = max(dpj,dpj-ci+ai); 河南理工大学ACM-ICPC培训o 二、完全背包n 每件物品可以选无限次for(int i = 1; i = n; +i) for(int j = ci; j = V; +j) dpj = max(dpj,dpj-ci + ai; o 注意：初始化方面的细节，如果要求恰好装满背包，那么在初始化时除了dp0为0其它dp1.V均设为-（求的是最大解，如果求的是最小解，则为

26、） 如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f0.V全部设为0。河南理工大学ACM-ICPC培训o 三、多重背包n每件物品可以选有限次 设每件物品的个数为counti;nO(V*log counti)写法（二进制优化）for(int i = 1; i = n; +i) int k; for(k = 1; k*2 = k*ci ; -j) dpj = max(dpj,dpj-k*ci + k*ai); k = counti + 1 - k; for(int j = V; j = k*ci; -j) dpj = max(dpj,dpj-k*ci + k*ai); 河南理工

27、大学ACM-ICPC培训o O(VN)的写法n /*此种方法求最大值不确定可否，但判断是否能将1-V内的背包装满可以*/int usedMAXN;for(int i = 1; i = N; +i) memset(used,0,sizeof(used); for(int j = ci; j = V; +j) if(usedj-ci counti & dpj dpj-ci + ai) dpj = dpj-ci + ai; usedj = usedj-ci + 1; /有待验证，估计不对，有兴趣的可以验证下河南理工大学ACM-ICPC培训o现在dpi用来表示容量为i的背包能否被所给物品恰好装满 上面

28、的01背包和完全背包以及上面一种O(V*log counti)的写法也可以做这样的改变memset(dp,false,sizeof(dp);dp0 = true;for(int i = 1; i = N; +i) memset(used,0,sizeof(used); for(int j = ci; j = V; +j) /注意这里是顺序的（和完全背包相同），其实多重背包也可以理解成被限制了的完全背包 if(!dpj & dpj-ci & usedj-ci counti) /注意这里的!dpj不能少 dpj = true; usedj = usedj-ci + 1; 河南理工大学ACM-ICPC培训o四、混合背包n以上三种背包的混合，有的物品只能取一次，有的物品能取无限次，有的物品能取有限次算法伪代码：for i=1.n if 第i件物品是01背包 for j=V.ci dpj=max(); /同上面01背包代码 else if 第i件物品是完全背包 for j=ci.V dpj=max(); /同上面完全背包 else if 第i件物品是多重背包 MultiplePack(ci