问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大(同样重量的铁和金子，你拿哪一个）。
设n个物品的重量和价值分别存储于数组w[]和v[]中，限制重量为tw。考虑一个n个字符的字符串“1111...000001”，其中第i个字符0 表示第i个物品没有选取，而1则表示第i个物品被选取。显然每一个这样的字符串等价于一个选择方案。用穷举法解决背包问题，穷举所有的选取方案，就可以得到问题的解。
</td> </tr> <tr> <td height="20" colspan="2">
下面是求解程序：
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