fac3_9.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 92 页，例
//0-1背包问题动态规划解法
class Math{
    public Math(){
   }
   static int min(int i,int j)
  {
   if(i>j)
   return j;
   else
   return i;
  }
  static int max(int i,int j)
  {
   if(i>j)
   return i;
   else
   return j;
  }
 }
 public class Fac3_9{
   public static void knapsack(int []v,int []w,int c,int [][]m)
   {
     int n=v.length-1;
     int jMax=Math.min(w[n]-1,c);
     for(int j=0;j<=jMax;j++)
        m[n][j]=0;
     for(int j=w[n];j<=c;j++)
        m[n][j]=v[n];
     for(int i=n-1;i>1;i--){
        jMax=Math.min(w[i]-1,c);
        for(int j=0;j<=jMax;j++)
          m[i][j]=m[i+1][j];
        for(int j=w[i];j<=c;j++)
          m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
       }
     m[1][c]=m[2][c];
     if(c>=w[1])
        m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);
   }
           
  public static void traceback(int [][]m,int []w,int c,int []x)
  { 
    int n=w.length-1;
    for(int i=0;i<n;i++)
        if(m[i][c]==m[i+1][c])x[i]=0;
        else { x[i]=1;
               c-=w[i];}
    x[n]=(m[n][c]>0)?1:0;
  }

      public static void main(String args[])
  {
    int v1[]={0,6,3,5,4,6};
    int w1[]={0,2,2,6,5,4};
    int c1=10;
    int n1=v1.length-1;
    int x1[]=new int[n1+1];
    int [][]m1=new int[n1+1][c1+1];
    knapsack(v1,w1,c1,m1);
    traceback(m1,w1,c1,x1);
    for(int i=1;i<=n1;i++)
     if(x1[i]==1)
    System.out.print(i+"  ");
    System.out.println();
    System.out.println(" 最优值= "+m1[1][c1]);
  }
}