LeetCode Day 44 Dynamic Programming (6/17)

Today, we move to a new area: Complete Knapsack Problem.

Complete Knapsack Problem

There are N items and a backpack that can carry at most W weights. The weight of the ith item is weight[i] and the value obtained is value[i] . There are an infinite number of each item (i.e., they can be put into the backpack many times), and solving for which items to put into the backpack has the greatest sum of item values.

The only difference between the Knapsack problem and the 01 Knapsack problem is that there are an infinite number of each item. the difference between the 01 Knapsack and the Knapsack is in the order of traversal.

# Iterate items first, then over the knapsack.
def test_CompletePack():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # 遍历物品
        for j in range(weight[i], bagWeight + 1):  # 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    print(dp[bagWeight])
 
test_CompletePack()
 
 
# Iterate knapsack first, then over the items
def test_CompletePack():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
 
    dp = [0] * (bagWeight + 1)
 
    for j in range(bagWeight + 1):  # 遍历背包容量
        for i in range(len(weight)):  # 遍历物品
            if j - weight[i] >= 0:
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
 
    print(dp[bagWeight])
 
test_CompletePack()

Questions

Question 1

518. Coin Change II

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Dynamic Programming in Five Parts:

1. Determine the dp array and the meaning of the subscripts
   1. dp[j]: the number of currency combinations that come together to make a total amount j is dp[j]
2. Determine the recursive formula
   1. dp[j] is the sum of all dp[j - coins[i]] (considering the case of coins[i]). So the recursive formula: dp[j] += dp[j - coins[i]];
3. How the dp array is initialised
   1. Firstly dp[0] must be 1, dp[0] = 1 is the basis of the recursive formula. If dp[0] = 0, all subsequent derivations will be zero.
4. Determining the order of traversal
   1. The outer for loop traverses the items (coins) and the inner for traverses the backpack (total money).
5. Example of deriving the dp array

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0]*(amount + 1)
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]
        return dp[amount]

Question 2

377. Combination Sum IV

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

If you’re looking for combinations, you’re looking for an outer for loop over the items, and an inner for loop over the backpack.

If you’re looking for permutations, it’s an outer for loop through the pack, and an inner for loop through the items.

If you put the traversal of the nums (items) in the outer loop, and the traversal of the target in the inner loop, for example, when calculating dp[4], there will only be sets like {1,3}, but not {3,1}, because the nums are traversed in the outer loop, and the 3s can only appear after the 1s!

So the final traversal order for this question is: target (the backpack) is placed in the outer loop, nums (the items) is placed in the inner loop, and the inner loop is traversed from front to back.

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):  
            for j in range(len(nums)):  
                if i - nums[j] >= 0:
                    dp[i] += dp[i - nums[j]]
        return dp[target]