Go语言视频零基础入门到精通

javalearner

背包问题
   

   

    问题描述：
      有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大(同样重量的铁和金子，你拿哪一个）。

     设n个物品的重量和价值分别存储于数组w[]和v[]中，限制重量为tw。考虑一个n个字符的字符串“1111...000001”，其中第i个字符0 表示第i个物品没有选取，而1则表示第i个物品被选取。显然每一个这样的字符串等价于一个选择方案。用穷举法解决背包问题，穷举所有的选取方案，就可以得到问题的解。
   

   

     下面是求解程序：
   

   

   

   
  
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;
   x=Integer.toBinaryString(i);//把b转化为二进制字符串
   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]+"放入背包   ");
     }
   
}
}
[/code] 程序运行结果：
C:java>java Test
这个背包问题的最优解是：
1111000001
价值最大值=30
3放入背包 5放入背包 7放入背包 10放入背包 2放入背包
C:java>
  

  
  
   
   

     
   

     
   
  

  

  










源码下载：http://file.javaxxz.com/2014/10/30/235929218.zip