动态规划算法：01背包问题

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

2、;printf(%dn ,fib( n ) ); 在上面的递归算法中存在多次计算同一个子问题,如：fib(2)。如果能将这样的子问题的解用数组保存起来，即可以加快求解的过程，即采用动态规划方法。/输出Fibonacii数列的第n项的动态规划算法#include #define MAX 50int fib(int n)int i,aMAX;a1=a2=1; for (i=3; i=n; i+)ai=ai-1+ai-2;return an;void main( )int n; scanf(%d,&n);printf(%dn ,fib( n ) );例1：0-1背包问题 有一个负重能力为m的背包和不

3、同价值vi、不同重量wi的物品n件。在不超过负重能力的前提下，从这n件物品中任意选择物品，使这些物品的价值之和最大。物品1234重量5321价值4431mij=mi+1j 当j=wi 算法思想1：设mij用来表示从第i项物品开始到第n项物品中区取出装入体积为j的背包的物品的最大价值。其中i的范围为1到n，其中j的范围为0到c，程序要寻求的解为m1c。可以发现： mnj 在当j=0并且j=wn 0 当j=0 并且 j wn/程序1：动态规划法#include #define MAX 20int n,c,wMAX,vMAX,mMAXMAX=0;void disp( )int i;for (i=1;

4、 i=n; i+)if ( mic!=mi+1c ) printf(%5d%5dn,wi,vi);void knapsack() int i,j; for (j=wn; j=1;i-) for (j=wi; jmi+1j-wi+vi ) mij=mi+1j; else mij=mi+1j-wi+vi; void main( )int i,j;printf(输入物品种数:); scanf(%d,&n);printf(输入每种物品的重量与价值:n);for (i=1; i=n; i+)scanf(%d%d,&wi,&vi);printf(输入背包的总重量:n); scanf(%d,&c); kna

5、psack(); disp();printf(最大价值=%dn,m0c);for (i=1; i=n; i+)for (j=0; j0且j0且j=wi 算法思想2：设mij用来表示从前i项物品中区取出装入体积为j的背包的物品的最大价值。其中i的范围为1到n，其中j的范围为0到c，程序要寻求的解为mnc。可以清楚地发现： m0j对所有的j的值为0， mi0对所有的i的值为0。 当前的体积j大于等于wi时， mij是下面两个量的最大值：mi-1j 和 mi-1j-wi+vi 当前的体积j小于wi时，mij等于mi-1j/程序2:动态规划法#include #define MAX 20int n,c

6、,wMAX,vMAX,mMAXMAX=0;void knapsack() int i,j; for (i=1; i=n; i+) for (j=1; j=wi-1 & mi-1j-wi-1+vi-1 mij ) mij=mi-1j-wi-1+vi-1;/显示所取的物品及其重量（其中一个解）/对数组m的最后一列检查来求解void disp( )int i,j;i=n;while ( mic=mi-1c ) i-;while (i0)j=i-1;while (mic-mjc!=vi-1 & j0) j-;printf(%5d%5dn,wi-1,vi-1);i=j;void main( )int i,j;printf(输入物品种数:); scanf(%d,&n);printf(输入每种物品的重量与价值:n);for (i=0; in; i+)scanf(%d%d,&wi,&vi);printf(输入背包的总重量:n); scanf(%d,&c); k