动态规划算法背包问题精.ppt
动态规划算法背包问题第1 页，本讲稿共12 页例：输出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);printf(%dn,fib(n);在上面的递归算法中存在多次计算同一个子问题,如：fib(2)。如果能将这样的子问题的解用数组保存起来，即可以加快求解的过程，即采用动态规划方法。第2 页，本讲稿共12 页/输出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);第3 页，本讲稿共12 页例1：0-1背包问题 有 一 个 负 重 能 力 为m 的 背 包 和 不 同 价 值vi、不 同 重 量wi的 物 品n 件。在 不 超 过 负 重 能 力 的 前 提 下，从 这n 件物品中任意选择物品，使这些物品的价值之和最大。物品1 2 3 4重量5 3 2 1价值4 4 3 1第4 页，本讲稿共12 页mij=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第5 页，本讲稿共12 页/程序1：动态规划法#include#define MAX 20int 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);第6 页，本讲稿共12 页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;第7 页，本讲稿共12 页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);knapsack();disp();printf(最大价值=%dn,m0c);for(i=1;i=n;i+)for(j=0;j=c;j+)printf(%3d,mij);printf(n);第8 页，本讲稿共12 页mij=0 i=0 或者 j=0mi-1j 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第9 页，本讲稿共12 页/程序2:动态规划法#include#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;第10 页，本讲稿共12 页/显示所取的物品及其重量（其中一个解）/对数组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;第11 页，本讲稿共12 页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);第12 页，本讲稿共12 页
