X6_DP & Knapsack

发表于   |   分类于 ，   |     |   阅读次数
§Problem

  • 322. Coin Change

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
        	int n = coins.size();
        	if (n == 0)
        		return -1;
        	sort(coins.rbegin(),coins.rend());
        	vector<int> dp(amount+1, amount+1);
        	dp[0] = 0;
        	for (auto coin : coins)
        		for (int w = coin; w <= amount; ++w)
        			dp[w] = min(dp[w], dp[w-coin]+1);
        	return dp[amount] > amount ? -1 : dp[amount];
        }
    };

    Others:

    1
    2
    3
    4
    // if coin[1000, 2000], there is no need for i starting at 0
    // coins[0] + 1 may overflow if coins[0] == Integer.MAX_VALUE
    		for (int i = coins[0]; i <= amount; i++) {
    			for (int coin : coins) {

  • 377. Combination Sum IV, similar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    public:
       int combinationSum4(vector<int>& nums, int target) {
        	int n = nums.size();
        	if (n == 0)
        		return 0;
        	sort(nums.begin(),nums.end());
        	vector<int> dp(target+1, 0);
        	dp[0] = 1;
            /* remove duplicate.
            eg. 1 1 2 = 1 2 1, since 1 will not consider again
        	for (auto num : nums)
        		for (int w = num; w <= target; ++w)
            */
            for (int w = nums[0]; w <= target; ++w)
                for (auto num : nums){
                    if (w < num)
                        break;
                    dp[w] += dp[w-num];
                }
        	return dp[target];
        }
    };

  • DP

    1. Deduction Formula
    2. Initialization
    3. Space Improvement (Bonus)
    • Audible 题：BugdetShopping

    n dollars, bundleQuantities array, bundleCosts array

    eg. Helen has n = 50 dollars to purchase notebooks from 2 stores described by bundleQunantities = [20, 19] and bundleCost = [24, 20]. She makes the following purchases:
    ​ One bundle of 20 notebooks from shop 0 at a cost 24 dollars and has 50 – 24 = 26 dollars left.
    ​ Another bundle of 20 notebooks from shop 0 at a cost 24 dollars and has 26 – 24 = 2 dollars left.
    Helen can’t afford any more notebooks, so we return the total number of notebooks she was able to purchase: 20 + 20 = 40.

    1
    2
    3
    // f(i) is the maximum number of notebook given i dollar
    f[i] = max(f[i – b.cost] + b.quantity) given different b
    maxf = 0, maxf = max(maxf, f[i])
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int max = 0;
    int[] f = new int[n + 1];
    for (int i = bundles[0].cost; i < f.length; i++) {
    	for (Bundle b : bundles) {
    		if (b.cost > i) {
    			break;
    		}

    		if (i == b.cost) {
    			f[i] = Math.max(f[i], b.quantity);
    			max = Math.max(max, f[i]);
    		}
    	
          	int c = f[i - b.cost];
    		if (c == 0) {
    			continue;
    		}

    		f[i] = Math.max(f[i], c + b.quantity);
    		System.out.println(i + "=" + f[i]);
    		max = Math.max(max, f[i]);
    	}
    }

Coin Change is unlimited, while Knapsack is limited

  • 背包问题

    1. Backpack
      Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
    1
    2
    3
    i = [0, A.length)
    	j = [m, A[i]]
    		result[j] = max(result[j-A[i]]+A[i], result[j])

    1. Backpack II
      Given n items with size Ai and value Vi, and a backpack with size m. What’s the maximum value can you put into the backpack?
      Example
      Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

      1
      2
      3
      i = [0, A.length)
      	j = [m, A[i]]
      		result[j] = max(result[j-A[i]]+v[i], result[j])

    2. https://en.wikipedia.org/wiki/Knapsack_problem
      https://www.geeksforgeeks.org/knapsack-problem
      https://brilliant.org/wiki/backpack-problem

  • 背包问题变种

    • 474. Ones and Zeroes

      maximize chossedn string -> m’s 1, n’s 0

      1
      2
      3
      for k=1..l
      	i=m..s0, j=n..s1
      		dp[i][j] = max(dp[i][j],dp[i-s0][j-s1]+1)// wo/w s

    • 494. Target Sum

      +/- ai = s

      1
      2
      3
      4
      5
      6
      7
      sum(P) - sum(N) = target           
      sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
      2 * sum(P) = target + sum(nums)

      for num:nums
      	for w = (t+s)/2 ... num
      		dp[w] += dp[w-num]

    • 416. Partition Equal Subset Sum

      find if the array can be partitioned into two subsets, that sum is equal

      1
      2
      3
      4
      5
      sum(subset1) = sum/2

      for num:nums
      	for w = sum/2 ... num
      		dp[w] = dp[w]|dp[w-num]
§Thinking

  • DP

    1. 先枚举物品，再枚举容量。
      eg. [1, 2, 3] 组合4时，(1, 1, 2) == (1, 2, 1)。因为同一个物体不会再次考虑

      1
      2
      3
      4
      5
      /* remove duplicate.
              eg. 1 1 2 = 1 2 1, since 1 will not consider again
          	for (auto num : nums)
          		for (int w = num; w <= target; ++w)
              */

    2. 先枚举容量，再枚举物品。

      1
      2
      for (int w = nums[0]; w <= target; ++w)
          for (auto num : nums)

  • 背包问题：

    1. 枚举物品
    2. 枚举容量
      增序枚举，重复装入某个物品，而且尽可能多的，使价值最大
      逆序枚举：物品至多装一次

  • 背包九讲