动态规划法解决01背包.doc

《动态规划法解决01背包.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析--01背包问题问题描述：给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能讲物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。问题分析：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数:(1)V(i,0)=V(0,

2、j)=0(2)V(i,j)=V(i-1,j)jwi(1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有以下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi的背包中的价值加上第i个物品的价值vi;(b)如果第i个物品没有装入背

3、包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。1#include3intV[200][200];//前i个物品装入容量为j的背包中获得的最大价值4intmax(inta,intb)5{6if(a>=b)7returna;8elsereturnb;9}1011intKnapSack(intn,intw[],intv[],intx[],intC)12{13inti,j;//式子（1）14f

4、or(i=0;i<=n;i++)15V[i][0]=0;16for(j=0;j<=C;j++)17V[0][j]=0;//式子（2）18for(i=0;i<=n-1;i++)19for(j=0;j<=C;j++)20if(j=0;i--)26{27if(V[i][j]>V[i-1][j])28{29x[i]=1

5、;30j=j-w[i];31}32else33x[i]=0;34}35printf("选中的物品是:");36for(i=0;i

6、rintf("请输入背包的最大容量:");53scanf("%d",&C);5455printf("输入物品数:");56scanf("%d",&n);57printf("请分别输入物品的重量:");58for(i=0;i

7、值为:");68printf("%d",s);697071}