背包算法--动态规划法

/*************************************************************************
*  Compilation:  javac Knapsack.java
*  Execution:    java Knapsack N W
*
*  Generates an instance of the 0/1 knapsack problem with N items
*  and maximum weight W and solves it in time and space proportional
*  to N * W using dynamic programming.
*
*  For testing, the inputs are generated at random with weights between 0
*  and W, and profits between 0 and 1000.
*
*  %  java Knapsack 6 2000
*  item    profit  weight  take
*  1       874     580     true
*  2       620     1616    false
*  3       345     1906    false
*  4       369     1942    false
*  5       360     50      true
*  6       470     294     true
*
*************************************************************************/

public class Knapsack {

   private int[] profit;
   private int[] weight;
   private int N;
   private int W;

   public Knapsack(int n, int w)
   {
     N = n;
W = w;
     dataGeneration();
   }
  
   private void dataGeneration()
   {
        profit = new int[N + 1];
        weight = new int[N + 1];

        // generate random instance, items 1..n
        for (int n = 1; n <= N; n++) {
            profit[n] = (int) (Math.random() * 1000);
            weight[n] = (int) (Math.random() * W);
        }
  
   }
  
   public boolean[][] doKnapsack()
   {
     // opt[n][w] = max profit of packing items 1..n with weight limit w
        // sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n?
        int[][] opt = new int[N + 1][W + 1];
        boolean[][] sol = new boolean[N + 1][W + 1];

        for (int n = 1; n <= N; n++) {
            for (int w = 1; w <= W; w++)
if (weight[n] <= w && (profit[n] + opt[n - 1][w - weight[n]] > opt[n - 1][w]))
{
   opt[n][w] = profit[n] + opt[n - 1][w - weight[n]];
   sol[n][w] = true;
}
else
{
   opt[n][w] = opt[n - 1][w];
   sol[n][w] = false;
}
        }
     return sol;
   }
   
public void print(boolean[][] sol)
{
// determine which items to take
        boolean[] take = new boolean[N + 1];
        for (int n = N, w = W; n > 0; n--) {
            if (sol[n][w]) { take[n] = true;  w = w - weight[n]; }
            else           { take[n] = false;                    }
        }

        // print results
        System.out.println("item" + "\t" + "profit" + "\t" + "weight" + "\t" + "take");
        for (int n = 1; n <= N; n++) {
            System.out.println(n + "\t" + profit[n] + "\t" + weight[n] + "\t" + take[n]);
        }
}

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);   // number of items
        int w = Integer.parseInt(args[1]);   // maximum weight of knapsack

        Knapsack app = new Knapsack(n, w);
        boolean[][] sol = app.doKnapsack();
        app.print(sol);
    }
}