01背包动态规划法

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

1、01背包动态规划法----------------------------精品word文档值得下载值得拥有----------------------------------------------0—1背包问题一、实验目的学习掌握动态规划法思想。二、实验内容用动态规划法求解0—1背包问题，并输出问题的最优解。0—1背包问题描述如下:给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。三、实验条件Jdk1.5以上四、需求分析对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大

2、化。五、基本思想:动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪婪算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。六、详细设计/**Dynamic_Programming.j

3、ava**Createdon2007年6月3日,下午4:13**Tochangethistemplate,chooseTools

4、TemplateManager*andopenthetemplateintheeditor.*/packagesunfa;/****@authorAdministrator*/publicclassDynamic_Programming{publicstaticvoidknapsack(int[]v,int[]w,intc,int[][]m){/**v[]w[]c分别是价值、重量、和背包容量数组m[i][j]表示有i~n个物品，背包容量为j的最大价值

5、。*/----------------------------精品word文档值得下载值得拥有-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------精品word文档值得下载值得拥有------------------------------

6、----------------intn=v.length-1;intjMax=Math.min(w[n]-1,c);for(intj=0;j<=jMax;j++)m[n][j]=0;//当w[n]>j有m[n][j]=0//m[n][j]表示只有n物品，背包的容量为j时的最大价值for(intl=w[n];l<=c;l++)m[n][l]=v[n];//当w[n]<=j有m[n][j]=v[n]//递规调用求出m[][]其它值，直到求出m[0][c]for(inti=n-1;i>=1;i--){jMax=Math.min(w[i]-1,c);for(intk=0;k<=jMa

7、x;k++)m[i][k]=m[i+1][k];for(inth=w[i];h<=c;h++)m[i][h]=Math.max(m[i+1][h],m[i+1][h-w[i]]+v[i]);}m[0][c]=m[1][c];if(c>=w[0])m[0][c]=Math.max(m[0][c],m[1][c-w[0]]+v[0]);}publicstaticvoidtraceback(int[][]m,int[]w,intc,int[]x){//根据最优值求出最优解intn=w.length-1;for(inti=0;i

8、x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c]>0)?1:0;}publicstaticvoidmain(String[]args){//测试int[]ww={2,2,6,5,4};int[]vv={6,3,5,4,6};int[][]mm=newint[5][11];----------------------------精品word文档值得下载值得拥有---------------------------------------------------