0-1 背包问题

image.png
使用贪心思想，优先放入平均价值最高的物品？ 这能够得到一个局部最优解，不一定是一个全局最优解。 无法解决这个问题
**
因为这道题存在两个变量。一个是容量。 一个是价值。 所以我们设置一个F（N，C）表示吧N个物品放入到C容量的背包里面，使得这个价值是最大的。

需要一个二维的数组来放里面的数组， 数组的大小是 N* C+1。横过来的表示每一个物品的坐标， 竖下来的是背包的容量。我们需要这根儿物品的重量要小于背包的容量才可以放进去。

image.png

  1. // 递归的写法
  2. public class Knapsack01 {
  3.     public int knapsack01(int[] w,int[] v, int c){
  4.         int n = w.length;
  5.         int[][] memo = new int[n][c+1];
  6.         return bestValue(w, v, n-1, c,memo);
  8.     }
  9.     // 用[0... index] 中的物品，填充容积为C的背包的最大价值
  10.     private int bestValue(int[] w, int[] v, int index, int c,int[][] memo) {
  11.         if(index<0 || c <= 0){
  12.             return 0;
  13.         }
  14.         if(memo[index][c]!= 0){
  15.             return memo[index][c];
  16.         }
  17.         int res = bestValue(w,v,index-1,c, memo);
  18.         if(c >= w[index]){
  19.             res = Math.max(res,v[index]+bestValue(w,v,index-1,c-w[index],memo));
  20.         }
  21.         memo[index][c] = res;
  22.         return res;
  24.     }
  25. }

动态规划的写法：

  1.     public int knapsack01(int[] w,int[] v, int c){
  2.         int n = w.length;
  3.         int[][] memo = new int[n][c+1];
  4.         if(n == 0){
  5.             return 0;
  6.         }
  7.         for (int i = 0; i <= c; i++) {
  8.             memo[0][i] = i>=w[0]? v[0]:0;
  9.         }
  11.         for (int i = 1; i < n; i++) {
  12.             for (int j = 0; j <= c; j++) {
  13.                 memo[i][j] = memo[i-1][j];
  14.                 if(j >= w[i]){
  15.                     memo[i][j] = Math.max(memo[i][j],v[i]+memo[i-1][j-w[i]]);
  16.                 }
  17.             }
  18.         }
  19.         return memo[n-1][c];
  20.     }