(精品)动态规划算法：0-1背包问题.ppt

《(精品)动态规划算法：0-1背包问题.ppt》由会员分享，可在线阅读，更多相关《(精品)动态规划算法：0-1背包问题.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、d main()int n;scanf(%d,&n);printf(%dn,fib(n);在上面的递归算法中存在多次计算同一个子问题,如：fib(2)。如果能将这样的子问题的解用数组保存起来，即可以加快求解的过程，即采用动态规划方法。/输出输出FibonaciiFibonacii数列的第数列的第n 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

3、,fib(n);例例1 1：0-10-1背包问题背包问题 有一个负重能力为m的背包和不同价值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 20in

4、t n,c,wMAX,vMAX,mMAXMAX=0;void disp()int i;for(i=1;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(输

5、入背包的总重量:n);scanf(%d,&c);knapsack();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:动态规划法动态规划法#i

6、nclude#define MAX 20int n,c,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);knapsack();disp();printf(最大价值=%dn,mnc);for(i=0;i=n;i+)for(j=0;j=c;j+)printf(%3d,mij);printf(n);