动态规划经典案例详解(背包问题)

4/4动态规划经典案例详解(背包问题)动态规划经典案例详解之背包问题

【

贪心准则3：价值密度pi/wi贪婪算法，这种选择准则为：从剩余物品中选择可装入包的pi/wi值最大的物品，但是这种策略也不能保证得到最优解。利用此策略解n=3,w=[20,15,15],p=[40,25,25],c=30时的得到的就不是最优解。

由以上的三种贪心策略可知，本题如果采用贪心方法求解，则完全取决于输入的数据，不管采用哪种方法都不能保证完全正确。

既然贪心不能解决，那么搜索行不行呢？我们可以深度搜索每种取物方案，然后依次对比得到的最终结果，取最大值即可。这个思路是正确的，结果也是可期的，但是时间代价是阶乘级的，当物品数量很多（N>10就已经需要很长时间了）时，所耗费的时间代价是巨大的，对于奥赛要求一秒钟内出解就根本不可能了，于是我们不得不想另外的思路，

【新思路】

要使物品价值最高，即p1*x1+p2*x1+...+pi*xi(其1=wi),f[i-1,j]}

这样，就可以自底向上地得出在前n件物品中取出若干件放进背包能获得的最大价值，也就是f[n,c]

【算法伪代码】

fori:=0tocdo{i=0也就是没有物品时清零}

f[0,i]:=0;

fori:=1tondo{枚举n件物品}

forj:=0tocdo{枚举所有的装入情况}

begin

f[i,j]:=f[i-1,j];{先让本次装入结果等于上次结果}

if(j>=w[i])and(f[i-1,j-w[i]]+p[i]>f[i,j]){如果能装第i件物品}

thenf[i,j]:=f[i-1,j-w[i]]+p[i];{且装入后价值变大则装入}

end;

writeln(f[n,c]);

【输入文件】

10

4

5143

40102530

【输出结果】下面列出所有的f[i,j]

0000404040404040

10101010405050505050

10101025405050506575

10103040405055708080

分析次结果，可以很清楚的了解整个程序的执行过程，最后的80就是本题的答案。

【实例1：开心的金明（NOIP2006普及组真题）】

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1...jk，则所求的总和为：v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单。

【输入文件】

输入的第1行，为两个正整数，用一个空格隔开：

Nm（其中N（0，表示该物品为附件，q是所属主件的编号）

【输出格式】

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

【输入样例】

10005

80020

40051

30051

40030

50020

【输出样例】

2200

【分析】

本题跟上题非常类似，可以确认用背包问题可以解决，但是难度却大大高于上题，这里提供两个思路。

简单方案：

对每一个物品做两种决策，取与不取。如果取，满足两个条件：1.要么它是主件，要么它所属的主件已经在包里了。2.放进去后的重要度与价格的成绩的总和要比没放进时的大。这两个条件缺一不可的。于是得到如下的动规方程：

f[i,j]:=f[i-1,j];

if(i为主件ori的主件在包中）and(f[i,j]<f[i,j-v]+v*w)

thenf[i,j]:=f[i,j-v]+v*w;

这个方案看似简单，其实有个非常复杂的问题，就是后一个条件“i的主件在包中”的判断，因为动态规划有个固有的弱点，就是很难知道整个中间过程，所以这个判断其实写起来是非常麻烦的。下面提供一个更好的方案：

改进方案：

细细的看题目，还一个很重要的条件我们还没用：“每个主件可以有０个，１个或２个附件”。也就是说对于一套物品（包含主件，所有的附件），我们称为一个属类，对一个属类的物品的购买方法，有以下５种：

１.一个都不买

２.主件

３.主件＋附件１

４.主件＋附件２

５.主件＋附件１＋附件２

这五种购买方法也是唯一的五种方法，也就是说对一属类的物品，我们只有上述的５种购买方法。于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品

的属类作为dp的状态。可以得到如下的dp方程：

f[i,j]=max{f[i-1,j];第1种情况

f[i-1,j-v[i,0]]+v[i,0]*w[i,0];第2种情况

f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1];第3种情况

f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2];第4种情况

f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];}第5种情况这种方法的DP效率大大提高，不过需要对输入数据进行重新处理，使之按属类重新编号。

注意题目中还有一个条件：“每件物品都是10元的整数倍”，利用它就可以把速度在提高十倍。

【例题3积木城堡】

XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。小XC是一个比他爸爸XC还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。

小XC想把自己垒的城堡送给幼儿园里漂亮的女孩子们，这样可以增加他的好感度。为了公平起见，他决定把送给每个女孩子一样高的城堡，这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。

任务：请你帮助小XC编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。

【输入格式】

第一行是一个整数N(N<=100)，表示一共有几座城堡。以下N行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。一座城堡中的积木不超过100块，每块积木的棱长不超过100。

【输出格式】

一个整数，表示最后城堡的最大可能的高度。如果找不到合适的方案，则输出0。

【输入样例】

2

21–1

321–1

【输出样例】

3

【分析】

本题初看也是可以用贪心法，但是跟之前的分析一样，贪心法是无法保证完全正确的。但是本次的背包思路不像前两个例子一样清楚，我们可以先把所有积木城堡的高度全部计算出来，为了要让所有城堡一样高，那么这个高度肯定小于或等于最低城堡的高度（设为min），如果我们把这个高度当成一个背包的容量，然后对N个城堡求以min最高高度所需要的最多积木数，通