0/1背包和多重背包问题

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

Screen Shot 2019-07-29 at 11.35.57 PM.png

// A Dynamic Programming based solution for 0-1 Knapsack problem 
class Knapsack 
{ 
   // Returns the maximum value that can be put in a knapsack of capacity W 
    static int knapSack(int W, int wt[], int val[], int n) 
    { 
         int i, w; 
     int K[][] = new int[n+1][W+1]; 
       
     // Build table K[][] in bottom up manner 
     for (i = 0; i <= n; i++) 
     { 
         for (w = 0; w <= W; w++) 
         { 
             if (i==0 || w==0) 
                  K[i][w] = 0; 
             else if (wt[i-1] <= w) 
                   K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
             else
                   K[i][w] = K[i-1][w]; 
         } 
      } 
       
      return K[n][W]; 
    } 
}

0/1背包问题，也可以被应用到求数组sum的问题，https://leetcode.com/problems/partition-equal-subset-sum/discuss/90592/01-knapsack-detailed-explanation
特点：选几个元素，拿到最大，能不能达到之类的。

多重背包问题

有一系列按钮，每个按钮按下去会得到一定体积范围的可乐。先给定一个目标体积范围，问不限制按按钮次数，能否确定一定能得到目标范围内的可乐？
举例：有三个按钮，按下去得到的范围是[100, 120], [200, 240], [400, 410],
假设目标是[100, 110], 那答案是不能。因为按下一，可能得到120体积的可乐，不在目标范围里。
假设目标是[90, 120]，那答案是可以。因为按下一，一定可以得到此范围内的可乐。
假设目标是[300, 360], 那答案是可以，因为按下一再按二，一定可以得到此范围内
假设目标是[310, 360], 那答案是不能，因为按下一再按二，有可能得到300，永远没可能确定得到这个范围内的可乐。
假设目标是[1, 9999999999]，那答案是可以。随便按一个都确定满足此范围。

public static boolean coke(List<List<Integer>> buttons, List<Integer> target) {
    int m = target.get(0);
    int n = target.get(1);
    boolean[][] dp = new boolean[m + 1][n + 1];
    
    //Init
    for (int i = 0; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        for (List<Integer> button : buttons) {
          if (i <= button.get(0) && j >= button.get(1)) {
            dp[i][j] = true;
            break;
          }
        }
      }
    }
  
    for (int i = 0; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        for (List<Integer> button : buttons) {
          int preL = i - button.get(0);
          int preR = j - button.get(1);
          if (preL >= 0 && preR >= 0 && dp[preL][preR]) {
            dp[i][j] = true;
           break;
          }
        }
      }
    }
    
    return dp[m][n];
  }

多重背包问题：每个可以拿多次，求上下节或者范围之类的，从拿到的数值入手。