LeetCode Day 42 Dynamic Programming (4/17)

To start the fourth day of practice, a new element will be covered at the beginning of the day: the Knapsack problem

1. Foundation of Knapsack problem

For example, let’s say 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]. Each item can only be used once, so solve for the items that will fit into the backpack with the greatest sum of values.

This is the standard Knapsack problem, so many students naturally think of knapsacks when they look at this, and don’t even know what the brute force solution should be.

This is actually not from the bottom up to think, but habitually think of the backpack, then the violent solution should be how?

Each item actually has only two states, take or not take, so you can use backtracking to search out all the cases, then the time complexity is $o(2^n)$, where n represents the number of items.

So the violent solution is exponential level time complexity. Further only then the solution of dynamic programming is needed for optimisation!

1.1 Two-dimensional dp arrays 01 knapsack problem

Still using the five-part dynamic programming analysis.

1. Determine the meaning of the dp array and subscripts.

For the Knapsack problem, one way to write it is to use a two-dimensional array, i.e., dp[i][j] means that any item taken from the subscripts [0-i] and put into the knapsack of capacity j, the maximum sum of values is what.

1. Determining the recursive formula

Recall the meaning of dp[i][j]: take any item from the subscript [0-i] and put it into the backpack of capacity j, what is the maximum sum of values.

Then there are two directions that can be pushed out to dp[i][j] that

Do not put item i: introduced by dp[i - 1][j], that is, the capacity of the backpack is j, the maximum value of not putting item i inside, at this time dp[i][j] is dp[i - 1][j]. (In fact, it means that when the weight of item i is greater than the weight of backpack j, item i cannot be put into the backpack, so the value in the backpack remains the same as before.) Putting item i: introduced by dp[i - 1][j - weight[i]], dp[i - 1][j - weight[i]] is the maximum value of not putting item i when the capacity of the backpack is j - weight[i], then dp[i - 1][j - weight[i]] + value[i] (the value of item i) is the value of the backpack to put item i to get the the maximum value of item i in the backpack So the recursive formula: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 3.

1. How the dp array is initialised

Regarding the initialisation, it must match the definition of the dp array, otherwise it will get messier and messier when it comes to recursive formulas.

First from the definition of dp[i][j], if the backpack capacity j is 0, that is, dp[i][0], no matter what items are selected, the sum of the backpack value must be 0.

Looking at the other cases: the state transfer equation dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); it can be seen that i is deduced from i-1, so it must be initialised when i is 0.

dp[0][j], i.e.: the maximum value that can be stored in a backpack of each capacity when i is 0 and the item numbered 0 is stored.

Then it is clear that when j < weight[0], dp[0][j] should be 0, because the capacity of the backpack is smaller than the weight of the numbered 0 item.

When j >= weight[0], dp[0][j] should be value[0], because the backpack capacity is sufficient for item number 0.

1. Determining Traversal Order

Iterate over items first, or over pack weights first? Actually, both! But traversing items first is better understood.

1. Deriving dp arrays as an example

The best way to do dynamic programming is to give an example on paper to derive the values of the corresponding dp array, and then write the code!

And we can have the code in Python:

def test_2_wei_bag_problem1(weight, value, bagweight):
    dp = [[0] * (bagweight + 1) for _ in range(len(weight))]

    for j in range(weight[0], bagweight + 1):
        dp[0][j] = value[0]

    for i in range(1, len(weight)):  
        for j in range(bagweight + 1):  
            if j < weight[i]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
 
    return dp[len(weight) - 1][bagweight]
 
if __name__ == "__main__":
 
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagweight = 4
 
    result = test_2_wei_bag_problem1(weight, value, bagweight)
    print(result)

1.2 Dynamic programming with one-dimensional rolling arrays

For the Knapsack problem actually the states are compressible.

When using two-dimensional arrays, the recursive formula: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

In fact, it can be found that if the layer of dp[i - 1] is copied onto dp[i], the expression could well be: dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

Instead of copying the layer dp[i - 1] to dp[i], it’s better to just use a one-dimensional array now, just dp[j] (a one-dimensional array, which can also be interpreted as a rolling array).

This is the origin of the rolling array, need to meet the condition that the previous layer can be reused, directly copied to the current layer.

Read here it is estimated that we have forgotten dp[i][j] in the i and j expression is what, i is the item, j is the backpack capacity.

dp[i][j] means take any item from the subscript [0-i], put it into the backpack with capacity j, what is the maximum sum of value.

def test_1_wei_bag_problem(weight, value, bagWeight):
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  
        for j in range(bagWeight, weight[i] - 1, -1):  
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
 
    return dp[bagWeight]
 
 
if __name__ == "__main__":
 
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagweight = 4
 
    result = test_1_wei_bag_problem(weight, value, bagweight)
    print(result)

2. LeetCode Question Practice

416. Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

The 01 Knapsack problem can be applied to this question only if the following four points are determined.

• The volume of the backpack is sum / 2
• The weight of the goods (elements in the set) to be put into the backpack is the value of the element, and the value of the element is also the value of the element.
• If the backpack is exactly full, you have found a subset of sum / 2.
• Each element in the backpack is not repeatable.

After finished analysing the above, we can apply 01 Knapsack problem to solve problem.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        _sum = 0
 
        dp = [0] * 10001
        for num in nums:
            _sum += num
        if _sum % 2 == 1:
            return False
        target = _sum // 2
        for num in nums:
            for j in range(target, num - 1, -1): 
                dp[j] = max(dp[j], dp[j - num] + num)
 
        if dp[target] == target:
            return True
        return False