代码如下:
public class knapsack { int max= 0; int ii =0; public void dp(int[]w,int[]v,int i,int sum,int portweight,int weight){ if(i<w.length&&(portweight+w[i])<=weight){ int sum1 = sum+v[i]; dp(w,v,i+1,sum1,portweight+w[i],weight); dp(w,v,i+1,sum,portweight,weight); } else{ if(sum>max){ max = sum; ii = i; } } } }当然，这个代码目前只可以求出最大价值，具体怎么选择商品，在求出最大值时，就是最后一个商品，此时可以得到该商品的下标，如上面的ii，然后扔掉商品ii，继续调用dp方法，直到ii为0. 具体方法如下:
public void reversedp(int[]w,int[]v,int weight){ dp(w,v,0,0,0,weight); if(ii!=0){ System.out.println("选择的重量"+w[ii-1]+" "+"选择的价值"+v[ii-1]); weight = weight - w[ii-1]; int []w1 = new int[w.length-1]; int []v1= new int[v.length-1]; int index = 0; for(int t = 0;t<w.length;++t){ if(t==ii-1){ continue; } w1[index] = w[t]; v1[index] = v[t]; index = index +1; } ii =0; max = 0; reversedp(w1,v1,weight); } }而对于自底向上的动态规划方法，我的分析是：
public void dp2(int[]w,int[]v,int weight){ int [][] res = new int[w.length][weight+1]; for(int i =0;i<w.length;++i){ for(int j =0;j<=weight;++j){ if(i==0){ if(j>=w[i]){ res[i][j] = v[i]; }else{ res[i][j] = 0; } }else{ if(j>=w[i]){ res[i][j] = res[i-1][j]>(v[i]+res[i-1][j-w[i]])? res[i-1][j]: (v[i]+res[i-1][j-w[i]]); } else{ res[i][j] =res[i-1][j]; } } } } reversedp2(res,w,v,3,50); //用于求出选择的商品 }其中reversedp2方法用于求出选择的商品，如果A[i,w]不等于A[i-1,w]则说明商品i被选择，除去商品i后继续对上一个商品进行判断。如果A[i,w]等于A[i-1,w]则说明商品i没有被选择，继续判断上一个商品。直到最后一个商品，大于0，则被选择，代码如下:
public void reversedp2(int res[][],int[]w,int[]v,int i,int weight){ if(i==0){ if(res[i][weight]>0){ System.out.println("选择的重量"+w[i]+" "+"价值"+v[i]); } } if(i>0){ if(res[i][weight]!=res[i-1][weight]){ System.out.println("选择的重量"+w[i]+" "+"价值"+v[i]); reversedp2(res,w,v,i-1,weight-w[i]); }else { reversedp2(res,w,v,i-1,weight); } } }
