0-1背包问题蛮力法求解(java版本)

时间:2023-02-14 04:24:21
sloves:
package BackPack;
public class Solves {
 public int[] DecimaltoBinary(int n,int m)
 {
  int r;//求余数
  int consult=1;//求商
  int j = 0;
  int []arr=new int[m];
  while (consult!=0)
  {
   consult = n / 2;
   r = n % 2;
   n = consult;
   arr[j] = r;
   j++;
  }
  return arr;
 }
 /**
  * 将求得的一位数组子集转换为二维数组
  * @param m
  * @return
  */
 public int[][] Subset(int m)
 {
  Solves s=new Solves();
  int subset[][]=new int[(int) Math.pow(2, m)][m];
  for (int i = 0; i <Math.pow(2, m); i++)
  {
   for (int j =0; j<m; j++)
   {
    subset[i][j]=s.DecimaltoBinary(i,m)[j];
   }
  }
    return subset;
 
 }
 public int MaxValue(int arr[])
 {
   int max = arr[0];
      for (int in = 0 ; in < arr.length; in++)
         {
           if( arr[in] > max)
           {
            max = arr[in];
           }
          }
  return max;
 
 }
}
 
demo:
package BackPack;
import java.util.Scanner;
public class Demo {
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int m;//物品的数量
  int capacity;//背包的容量
  int wb=0;//初始化背包的质量
  int vb=0;//初始化背包的价值
  Solves s=new Solves();
     Scanner sc=new Scanner(System.in);
     System.out.print("请输入物品的数量:");
     m=sc.nextInt();
     System.out.print("请输入背包的容量:");
     capacity=sc.nextInt();
     int weight[]=new int[m];//用来记录每个物品的重量
     int value[]=new int[m];//用来记录每个物品的价值
     for(int i=0;i<m;i++)
     {
      System.out.print("请输入物品"+i+"的重量:");
      weight[i]=sc.nextInt();
      System.out.print("请输入物品"+i+"的价值:");
      value[i]=sc.nextInt();
     }
     int MaxValue[]=new int[(int)Math.pow(2, m)];
     System.out.println("各个方案如下:");
     for (int i = 0; i <Math.pow(2, m); i++)
  {
   for (int j =0; j<m; j++)
   {
       if(s.Subset(m)[i][j]==1)
       {
        wb+=weight[j]*s.Subset(m)[i][j];
        vb+=value[j];
        System.out.print("物品:"+j+"");
       }
   }
 
   
   if(wb<=capacity)
   {
    MaxValue[i]=wb;
      System.out.println("------"+"方案"+i+":总价值为:"+vb+" "+"总重量为:"+wb);
   }
   else
   {
     System.out.println("------"+"方案"+i+":超出背包容量!");
   }
   
   wb=0;
   vb=0;
  }
    System.out.println("背包可装入的最大容量为:"+s.MaxValue(MaxValue));
 }
}