Java 数据结构 - 背包问题

以下是使用动态规划技术在 Java 中解决背包问题的方案。

示例

public class KnapsackExample {
   static int max(int a, int b) { 
      return (a > b)? a : b; 
   }
   public static int knapSack(int capacity, int[] items, int[] values, int numOfItems ) {
      int i, w;
      int [][]K = new int[numOfItems+1][capacity+1];

      // Build table K[][] in bottom up manner
      for (i = 0; i <= numOfItems; i++) {
         for (w = 0; w <= capacity; w++) {
            if (i==0 || w==0) {
               K[i][w] = 0;
            } else if (items[i-1] <= w) {
               K[i][w] = max(values[i-1] + K[i-1][w-items[i-1]],  K[i-1][w]);
            } else {
               K[i][w] = K[i-1][w];
            }
         }
      }
      return K[numOfItems][capacity];
   }
   public static void main(String args[]) {
      int[] items = {12, 45, 67, 90, 45};
      int numOfItems = items.length;
      int capacity = 100;
      int[] values = {1200, 4500, 6700, 9000, 4500}; 
      
      int x = knapSack(capacity, items, values, numOfItems );
      System.out.println(x);	   
   }
}

输出

9000