下面是求解程序:
public class Test{ public static void main(String args[]){ int maxv=0; //价值最大值 int tw=30;//背包限制重量 int w[]={3,5,7,10,15,20,25,6,8,2};//物品的重量,假设有10个物品 int v[]={10,6,5,8,4,6,12,3,2,1};//物品的价值 String x="";//二进制字符串,对应一种选择方案 String result="";//存放最佳解 int b[]=new int[1024];//共有1024种选取物品的方案 for (int i=0;i< 1024;i++) { b[i]=i; x=Integer.toBinaryString(i);//把b[i]转化为二进制字符串 int temp_w=0; int temp_v=0; for (int k=0;k< x.length();k++){ if (x.charAt(k)=='1'){ temp_w=temp_w+w[k]; temp_v=temp_v+v[k]; } } if ((temp_w< =tw)&&(temp_v>maxv)) { maxv=temp_v; result=x;//保存该择选方案 } } System.out.println("这个背包问题的最优解是:"); System.out.print(result); System.out.println(); System.out.println("价值最大值="+maxv); for(int k=0;k< result.length();k++){ if(result.charAt(k)=='1') System.out.print(w[k]+"放入背包 "); } } }
程序运行结果:
C:\java>java Test
这个背包问题的最优解是:
1111000001
价值最大值=30
3放入背包 5放入背包 7放入背包 10放入背包 2放入背包
C:\java>
↑返回目录
前一篇: 万年历程序
后一篇: java产生UUID