01背包问题动态规划算法

算法分析与设计实验报告

第3次实验

姓名 学号 班级

时间 11.14下午 地点 四合院

实验名称

动态规划法求解背包问题

实验目的 通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计。

利用动态规划算法求解背包问题，并计算出程序运行所需要的时间。

实验原理 给定几组数据，利用动态规划算法的思想，把0-1 背包装满并使得其价值最大。

实验步骤

① 把问题分解成若干个子问题，如背包仅可以容纳 1 个物品且可以容纳的质量为一等。

② 依次求出各个子问题的最优解。

③ 每个子问题的最优解又可以从它的子问题的最优解中得到。

④ 通过各个子问题的最优解得到原问题的最优解。

关键代码 void KnapSack(int n,int w[],int v[],int x[],int C)

{

int i,j;

int jMax=min(w[n]-1,C);

for(j=0;j<=jMax;j++)

mV[n][j]=0;

for(j=w[n];j<=C;j++)

mV[n][j]=v[n];

for(i=n-1;i>1;i--)

{

jMax=min(w[n]-1,C);

for(j=0;j<=jMax;j++)

mV[i][j]=mV[i+1][j];

for(j=w[i];j<=C;j++)

mV[i][j]=max(mV[i+1][j],mV[i+1][j-w[i]]+v[i]);

}

mV[1][C]=mV[2][C];

if(C>=w[1])

mV[i][j]=max(mV[1][C],mV[2][C-w[1]]+v[1]);

第３５卷第４期　２０１６年ｌ２月　中南民族大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｕｔｈ　Ｃｅｎｔｒａｌ　Ｕｎｉｖｅｒｓｉｔｙ　ｆｏｒ　Ｎａｔｉｏｎａｌｉｔｉｅｓ（Ｎａｔ．Ｓｃｉ．Ｅｄｉｔｉｏｎ）　Ｖ０１．３５　Ｎｏ．４　Ｄｅｃ．２０１６　

背包问题的动态规划改进算法　

蓝雯飞，吴子莹，杨　波　

（中南民族大学计算机科学学院，武汉４３００７４）　摘要在动态规划算法的基础上提出了改进算法，对于０－１背包问题，改进了动态规划算法的状态表示以减少需　要计算的状态个数来求解该问题；对于完全背包问题，简化了动态规划算法状态的决策依赖关系来求解该问题．实　验结果表明：所提出的改进算法在时空效率上具有一定的有效性和优越性．　关键词背包问题；动态规划；状态表示；决策依赖　中图分类号ＴＰ３０１　文献标识码Ａ文章编号１６７２－４３２１（２０１６）０４－０１０１－０５　

Ｉｍｐｒｏｖｅｄ　Ｄｙｎａｍｉｃ　Ｐｒｏｇｒａｍｍｉｎｇ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｔｈｅ　Ｋｎａｐｓａｃｋ　Ｐｒｏｂｌｅｍ　

Ｌａｎ耽　，Ｗｕ　Ｚｉｙｉｎｇ，　Ｂ。　（ＣｏＨｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｓｏｕｔｈ－Ｃｅｎｔｒａｌ　Ｕｎｉｖｅｒｓｉｔｙ　ｆｏｒ　Ｎａｔｉｏｎａｌｉｔｉｅｓ，Ｗｕｈａｎ　４３００７４，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ　Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｗｅ　ｐｒｏｐｏｓｅｄ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ｔｈｉｎｋｉｎｇ．Ｆｏｒ　ｔｈｅ　０－１　ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ，ｗｅ　ｉｍｐｒｏｖｅｄ　ｔｈｅ　ｓｔａｔｕｓ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ｏｆ　ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｓｔａｔｅｓ　ｎｅｅｄｅｄ　ｔｏ　ｃａｌｃｕｌａｔｅ．Ｆｏｒ　ｔｈｅ　ｃｏｍｐｌｅｔｅ　ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ，ｗｅ　ｓｉｍｐｌｉｆｉｅｄ　ｔｈｅ　ｄｅｃｉｓｉｏｎ　ｄｅｐｅｎｄｅｎｃｙ　ｓｔａｔｕｓ　ｏｆ　ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗｅｄ　ｔｈａｔ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍｓ　ｈａｖｅ　ｓｏｍｅ　ｖａｌｉｄｉｔｙ　ａｎｄ　ｓｕｐｅｒｉｏｒｉｔｙ　ｉｎ　ｓｐａｃｅ　ａｎｄ　ｔｉｍｅ　ｅｆｆｉｃｉｅｎｃｙ．　Ｋｅｙｗｏｒｄｓ　ｋｎａｐｓａｃｋ　ｐｒｏｂｌｅｍ；ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ；ｓｔａｔｅ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ；ｄｅｃｉｓｉｏｎ　ｄｅｐｅｎｄｅｎｃｙ　

动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。

比如01背包问题。

因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。

测试数据：

10,3

3,4

4,5

5,6

c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.

这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)

从以上最大价值的构造过程中可以看出。

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?

下面是实际程序:

#include

int c[10][100];

int knapsack(int m,int n)

{

int i,j,w[10],p[10]; for(i=1;i

scanf("\n%d,%d",&w[i],&p[i]);

for(i=0;i<10;i++)

for(j=0;j<100;j++)

动态规划——01背包问题

⼀、最基础的动态规划之⼀

01背包问题是动态规划中最基础的问题之⼀，它的解法完美地体现了动态规划的思想和性质。

01背包问题最常见的问题形式是：给定n件物品的体积和价值，将他们尽可能地放⼊⼀个体积固定的背包，最⼤的价值可以是多少。我们可以⽤费⽤c和价值v来描述⼀件物品，再设允许的最⼤花费为w。只要n稍⼤，我们就不可能通过搜索来遍查所有组合的可能。运⽤动态规划的思想，我们把原来的问题拆分为⼦问题，⼦问题再进⼀步拆分直⾄不可再分（初始值），随后从初始值开始，尽可能地求取每⼀个⼦问题的最优解，最终就能求得原问题的解。由于不同的问题可能有相同的⼦问题，⼦问题存在⼤量重叠，我们需要额外的空间来存储已经求得的⼦问题的最优解。这样，可以⼤幅度地降低时间复杂度。

有了这样的思想，我们来看01背包问题可以怎样拆分成⼦问题：

要求解的问题是：在n件物品中最⼤花费为w能得到的最⼤价值。显然，对于0 <= i <= n,0 <= j <= w，在前i件物品中最⼤花费为j能得到的最⼤价值。

可以使⽤数组dp[n + 1][w + 1]来存储所有的⼦问题，dp[i][j]就代表从前i件物品中选出总花费不超过j时的最⼤价值。

可知dp[0][j]值⼀定为零。那么，该怎么递推求取所有⼦问题的解呢。显⽽易见，要考虑在前i件物品中拿取，⾸先要考虑前i - 1件物品中拿取的最优情况。

当我们从第i - 1件物品递推到第i件时，我们就要考虑这件物品是拿，还是不拿，怎样收益最⼤。

①：⾸先，如果j < c[i]，那第i件物品是⽆论如何拿不了的，dp[i][j] = dp[i - 1][j];

②：如果可以拿，那就要考虑拿了之后收益是否更⼤。拿这件物品需要花费c[i]，除去这c[i]的⼦问题应该是dp[i - 1][j - c[i]]，这时，就要⽐较dp[i - 1][j]和dp[i - 1][j - c[i]] + v[i]，得出最优⽅案。