动态规划算法：0-1背包问题

《动态规划算法：0-1背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划算法原理将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来。为了不去求解相同的子问题，引入一个数组，把所有子问题的解存于该数组中，这就是动态规划所采用的基本方法。动态规划采用由下至上(Bottom-Up)计算策略。例：输出Fibonacii数列的第n项的递归算法#includeintfib(intn){if(n<=1)return1;elsereturnfib

2、(n-1)+fib(n-2);}voidmain(){intn;scanf("%d",&n);printf("%d",fib(n));}在上面的递归算法中存在多次计算同一个子问题,如：fib(2)。如果能将这样的子问题的解用数组保存起来，即可以加快求解的过程，即采用动态规划方法。//输出Fibonacii数列的第n项的动态规划算法#include#defineMAX50intfib(intn){inti,a[MAX];a[1]=a[2]=1;for(i=3;i<=n;i++)a

3、[i]=a[i-1]+a[i-2];returna[n];}voidmain(){intn;scanf("%d",&n);printf("%d",fib(n));}例1：0-1背包问题有一个负重能力为m的背包和不同价值v[i]、不同重量w[i]的物品n件。在不超过负重能力的前提下，从这n件物品中任意选择物品，使这些物品的价值之和最大。物品1234重量5321价值4431m[i][j]=m[i+1][j]当j=w[

4、i]算法思想1：设m[i][j]用来表示从第i项物品开始到第n项物品中区取出装入体积为j的背包的物品的最大价值。其中i的范围为1到n，其中j的范围为0到c，程序要寻求的解为m[1][c]。可以发现：①m[n][j]在当j>=0并且j

5、v[n]当j>=w[n]0当j>=0并且j#defineMAX20intn,c,w[MAX],v[MAX],m[MAX][MAX]={0};voiddisp(){inti;for(i=1;i<=n;i++)if(m[i][c]!=m[i+1][c])printf("%5d%5d",w[i],v[i]);}voidknapsack(){inti,j;for(j=w[n];j<=c;j++)m[n][j]=v[n];for(i=n-1

6、;i>=1;i--)for(j=w[i];j<=c;j++)if(m[i+1][j]>m[i+1][j-w[i]]+v[i])m[i][j]=m[i+1][j];elsem[i][j]=m[i+1][j-w[i]]+v[i];}voidmain(){inti,j;printf("输入物品种数:");scanf("%d",&n);printf("输入每种物品的重量与价值:");for(i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);printf("输入背包的总重量:

7、n");scanf("%d",&c);knapsack();disp();printf("最大价值=%d",m[0][c]);for(i=1;i<=n;i++){for(j=0;j<=c;j++)printf("%3d",m[i][j]);printf("");}}m[i][j]=0i=0或者j=0m[i-1][j]j>0且j0且j>=w[i]算法思想2：设m[i][j]用来表示从前i项物品中区取出装入体积为j

8、的背包的物品的最大价值。其中i的范围为1到n，其中j的范围为0到c，程序要寻求的解为m[n][c]。可以清楚地发现：①m[0][j]对所有的j的值为0，m[i][0]对所有的i的值为0。②当前的体积j大于等于w[i]时，m[i][j]是下面两个量的最大值：m[i-1][j]和m[i-1][j-w[i]]+v[i]③当前的体积j小于w[i]时，m[i][j]等于m[i-1][j]//程序2:动态规划法#include#defineMAX20intn,c