贪心法和回溯法 求解“背包、0/1背包问题”——Java 实现

给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?

贪心算法描述：

1.改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列； 

     2.将数组x[n]初始化为0； //初始化向量 

     3.   i=1;

     4.循环直到（w[i]>C);

         4.1    x[i]=1;

         4.2    C=C-w[i];

         4.3     i++;

    5.   x[i]=C/w[i];

KnapSack1.java                                  //贪心算法


import java.util.*;


public class KnapSack1
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  System.out.println("Please enter the number of objects(请输入物品的数量):");
  int n=in.nextInt();
  int[] w=new int[n];
  int[] v=new int[n];
  System.out.println("Now,please enter the weight of these objects(现在请输入这些物品的重量):");
  for(int i=0;i<n;i++)
  {
   w[i]=in.nextInt();
  }
  System.out.println("Now,please enter the value of these objects(现在请输入这些物品的价值):");
  for(int i=0;i<n;i++)
  {
   v[i]=in.nextInt();
  }
  System.out.println("Now,please enter the capacity of the pack(现在请输入背包的容量):");
     int c=in.nextInt();
     /**
      *按单位重量价值r[i]=v[i]/w[i]降序排列
      */
     double startTime=System.currentTimeMillis();
  double[] r=new double[n];
  int[] index=new int[n];
  for(int i=0;i<n;i++)
  {
   r[i]=(double)v[i]/(double)w[i];
   index[i]=i;
  }
  double temp=0;
  for(int i=0;i<n-1;i++)
  {
   for(int j=i+1;j<n;j++)
   {
    if(r[i]<r[j])
    {
     temp=r[i];
     r[i]=r[j];
     r[j]=temp;
     int x=index[i];
     index[i]=index[j];
     index[j]=x;
    }
   }
  }
  /**
   *排序后的重量和价值分别存到w1[]和v1[]中
   */
  int[] w1=new int[n];
  int[] v1=new int[n];
  for(int i=0;i<n;i++)
  {
   w1[i]=w[index[i]];
   v1[i]=v[index[i]];
  }
  System.out.println (Arrays.toString(w1));
  System.out.println (Arrays.toString(v1));
  /**
   *初始化解向量x[n] 
   */ 
  int[] x=new int[n];
  for(int i=0;i<n;i++)
  {
   x[i]=0;
  }
  /**
   *求解并打印解向量
   */
  for(int i=0;i<n;i++)
  {
   if(w1[i]<c)
   {
    x[i]=1;
    c=c-w1[i];
   }
  }
  System.out.println("The solution vector is(解向量是):"+Arrays.toString(x));
  /**
   *根据解向量求出背包中存放物品的最大价值并打印
   */
  int maxValue=0;
  for(int i=0;i<n;i++)
  {
   if(x[i]==1)
    maxValue+=v1[i];
  }
  double endTime=System.currentTimeMillis();
  System.out.println("Now,the largest values of objects in the pack is(背包中物品的最大价值为):"+maxValue);
  System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
 }
}

***********************************************************************************************

回溯算法描述： 

1.将各物品按单位重量价值从大到小排序； 

     2.bestP=0;

     3.BackTrack(1);

     4.输出背包的最大值bestP;

     BackTrack(int i)

       1.   if(i>n){

                     if(bestP<cp) bestP=cp;

                     return;

               }

       2.若（cw+w[i]<=C,则       //进入左子树             

             2 .1   cw=cw+w[i];

             2.2    cp=cp+p[i];

             2.3    BackTrack(i+1);

             2.4     cw=cw-w[i]; cp=cp-p[i];

KnapSack2.java                                                   // 回溯算法


import java.util.*;

public class KnapSack2
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  System.out.println("Please enter the number of objects(请输入物品的数量):");
  int n=in.nextInt();
  int[] w=new int[n];
  int[] v=new int[n];
  System.out.println("Now,please enter the weight of these objects(现在请输入这些物品的重量):");
  for(int i=0;i<n;i++)
  {
   w[i]=in.nextInt();
  }
  System.out.println("Now,please enter the value of these objects(现在请输入这些物品的价值):");
  for(int i=0;i<n;i++)
  {
   v[i]=in.nextInt();
  }
  System.out.println("Now,please enter the capacity of the pack(现在请输入背包的容量):");
     int c=in.nextInt();
     /**
      *按单位重量价值r[i]=v[i]/w[i]降序排列
      */
     double startTime=System.currentTimeMillis();
  double[] r=new double[n];
  int[] index=new int[n];
  for(int i=0;i<n;i++)
  {
   r[i]=(double)v[i]/(double)w[i];
   index[i]=i;
  }
  double temp=0;
  for(int i=0;i<n-1;i++)
  {
   for(int j=i+1;j<n;j++)
   {
    if(r[i]<r[j])
    {
     temp=r[i];
     r[i]=r[j];
     r[j]=temp;
     int x=index[i];
     index[i]=index[j];
     index[j]=x;
    }
   }
  }
  /**
   *排序后的重量和价值分别存到w1[]和v1[]中
   */
  int[] w1=new int[n];
  int[] v1=new int[n];
  for(int i=0;i<n;i++)
  {
   w1[i]=w[index[i]];
   v1[i]=v[index[i]];
  }
  System.out.println (Arrays.toString(w1));
  System.out.println (Arrays.toString(v1));
  /**
   *调用函数KnapSackBackTrack()，输出打印装完物品以后的最大价值
   */
  KnapSackBackTrack(w1,v1,w1.length,c);
  double endTime=System.currentTimeMillis();
  System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");  
 }
 /**
  *用回溯法求0、1背包最大价值的函数定义
  */
 public static void KnapSackBackTrack(int[] w,int[] v,int n,int c)
 {
  int CurrentWeight=0;
  int CurrentValue=0;
  int maxValue=0;
  int i=0;
  while(i>=0)
  {
   if(CurrentWeight+w[i]<=c)
   {
    CurrentWeight+=w[i];
    CurrentValue+=v[i];
    i++;
   }
   else
    break;   
  }
  if(i<n)
  {
   maxValue=CurrentValue;
   System.out.println("Now,the largest values of objects in the pack is(背包中物品的最大价值为):"+maxValue);
   return;
  }
  System.out.println("Now,the largest values of objects in the pack is(背包中物品的最大价值为):"+maxValue);
  return;
 }
}

评论

3 楼 adam_zs 2013-01-09  

程序有问题、

2 楼 adam_zs 2013-01-09  

结果错了....

1 楼 我们都有病 2011-06-10  

你这个01背包不对吧？？？
如果重量是  7 3 3 3
   价值是   8 3 3 3
   背包容量是  9  的话

最大价值应该是 9吧  而你的是8

你的算法没有考虑这个问题！！！