Leetcode: 0-1 knapsack problem in dynamic programming [come and set the template directly]

PS. 0-1 Knapsack problem is undoubtedly a very classic class of dynamic programming problems , Here is a template for solving this kind of problem . This article is for reference Random code recording Some notes made , Please stamp the link for the full version .

standard 0-1 knapsack problem

Two dimensional array solution

Standard knapsack problem ： Yes n Items and one can carry a maximum weight of w The backpack . The first i The weight of the item is weight[i], The value is value[i]. Each item can only be used once , Solve which items are loaded into the backpack, and the total value of the items is the largest .

Each item actually has only two states , Take it or not , So you can use the backtracking method to search all the cases , So time complexity is $o(2^n)$, there $n$ The number of items . So the solution to violence is exponential time complexity , So we need the solution of dynamic programming to optimize ！

for instance ： The maximum weight of the backpack is 4. Item is ：

What's the maximum value of the items a backpack can carry ？

dp[i][j] Indicates from subscript [0-i] Take whatever you want from your belongings , Put in capacity j The sum of the maximum value of the backpack .

The recursive formula ： There are two directions to push out dp[i][j]：

• No objects i： from dp[i - 1][j] Introduction , The capacity of the backpack is j, There are no items in it i Maximum value of , here dp[i][j] Namely dp[i - 1][j].（ It's actually when things i It weighs more than a backpack j When the weight of , goods i Can't put it in the backpack , So the value in the backpack is still the same as before .)
• Put things i： from dp[i - 1][j - weight[i]] Introduction ,dp[i - 1][j - weight[i]] The capacity of the backpack is j - weight[i] Don't put things when you are i Maximum value of , that dp[i - 1][j - weight[i]] + value[i]（ goods i The value of ）, Is to put things in your backpack i Get the most value .

So the recursive formula ： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]).

initialization ：

1. from dp[i][j] Starting from the definition of , If the backpack capacity j by 0 Words , namely dp[i][0], No matter what items you choose , The total value of the backpack must be 0.
2. As can be seen from the state transition equation i By i-1 derived , that i by 0 Be sure to initialize .dp[0][j], namely ：i by 0, Storage number 0 When you get your stuff , The maximum value that a backpack of each capacity can store . So obviously when j < weight[0] When ,dp[0][j] Should be 0, Because the backpack has more capacity than the number 0 The weight of the goods is still small . When j >= weight[0] when ,dp[0][j] Should be value[0], Because the backpack has enough capacity to put numbers 0 goods .

Initialization code ：

for i in range(rows):
    dp[i][0] = 0
    
for i in range(1, cols):
    if i >= weight[0]:
         dp[0][i] = value[0]

This problem has two traversal dimensions ： Item and backpack weight . that , First traverse the items or the weight of the backpack ？ In fact, it can be ！！

Go through the items first , Then traverse the backpack weight ：

for i in range(1, len(weight)):
    for j in range(1, bag_size + 1):
        if weight[i] > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

Go through the backpack first , Then traverse the items ：

for i in range(1, bag_size + 1):
    for j in range(1, len(weight)):
        if weight[j] > i:
            dp[j][i] = dp[j - 1][i]
        else:
            dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - weight[j]] + value[j])

The complete code is as follows ：

#  The maximum weight of the backpack is 4. Item is ：
#  weight   value 
#  goods 0 1 15
#  goods 1 3 20
#  goods 2 4 30
#  What's the maximum value of the items a backpack can carry ？

"""  Two dimensional array implementation  dp[i][j]  Indicates from subscript [0-i] Take whatever you want from your belongings , Put in capacity j The backpack , What is the maximum total value . """


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

    for i in range(len(weight)):
        dp[i][0] = 0

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

    #  Go through the backpack first 
    for i in range(1, bag_size + 1):
        for j in range(1, len(weight)):
            if weight[j] > i:
                dp[j][i] = dp[j - 1][i]
            else:
                dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - weight[j]] + value[j])

    #  Go through the items first 
    for i in range(1, len(weight)):
        for j in range(1, bag_size + 1):
            if weight[i] > j:
                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][bag_size]


if __name__ == '__main__':
    bag_size = 4
    weight = [1, 3, 4]
    value = [15, 20, 30]
    ret = test_2_wei_bag_problem1(bag_size, weight, value)
    print(ret)

One dimensional array solution

For the knapsack problem, the state can be compressed . 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 dp[i - 1] Copy that layer to dp[i] On , The expression can be ：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]). Instead of putting dp[i - 1] Copy this layer to dp[i] On , Let's just use one-dimensional array , Only dp[j].

This is it. Scrolling array The origin of , The condition to be met is that the upper layer can be reused , Copy directly to the current layer .

Restate the definition ：dp[i][j]** Indicates from subscript **[0-i] Take whatever you want from your belongings , Put in capacity j The backpack , What is the maximum total value .

that , In one dimension dp Array ,dp[j] Express ： Capacity of j The backpack , The value of the items carried can be up to dp[j].

dp[j] Can pass dp[j - weight[i]] derived ,dp[j - weight[i]] The capacity is j - weight[i] The maximum value of your backpack .dp[j - weight[i]] + value[i] The capacity is j - goods i weight The backpack Add items i The value of .（ That is, the capacity is j The backpack , Put something in i After that, the value is ：dp[j]）

here dp[j] There are two choices ：

1. One is to take yourself dp[j], This is equivalent to dp[i-1][j], I.e. no objects i;
2. One is to take dp[j - weight[i]] + value[i], That is to put things i.

Specify the maximum , You can get dp[j].

So the recursive formula is ：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]).

initialization ：

1. dp[0] It should be 0, Because the backpack has a capacity of 0 The greatest value of the items carried is 0;
2. The rest is initialized to 0 that will do , Because we can see from the recursive formula , Other dp Will be covered .

traversal order ： A two-dimensional dp When traversing , Backpack capacity is from small to large , and A one-dimensional dp When traversing , Backpacks are from big to small . Why? ？ Traversal in reverse order is to ensure that items i Only once ！. But if once the positive order traverses , So the object 0 Will be repeated many times ！

Let's look at two nested for The order of the cycle , The code must first traverse the items and then nest and traverse the backpack capacity , You can't traverse the backpack capacity and nested items first ！ Because one dimension dp Writing , Backpack capacity must be traversed in reverse order , If the traversal backpack capacity is placed on the upper layer , Then each dp[j] Only one item will be put in , namely ： There is only one item in the backpack .

One dimensional array code ：

#  The maximum weight of the backpack is 4. Item is ：
#  weight   value 
#  goods 0 1 15
#  goods 1 3 20
#  goods 2 4 30
#  What's the maximum value of the items a backpack can carry ？

"""  One dimensional array implementation  dp[j] Express ： Capacity of j The backpack , The value of the items carried can be up to dp[j] """


def wei_bag_problem1(bag_size, weight, value):
    dp = [0 for _ in range(bag_size + 1)]

    #  Go through the items first ,  And then traverse the backpack 
    for i in range(len(weight)):
        for j in range(bag_size, i, -1): 
            if j >= weight[i]:
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    return dp[-1]


if __name__ == '__main__':
    bag_size = 4
    weight = [1, 3, 4]
    value = [15, 20, 30]
    ret = wei_bag_problem1(bag_size, weight, value)
    print(ret)

Classic title

416. To divide into equal and subsets

To give you one Contains only positive integers Of Non empty Array nums . Please decide whether you can divide this array into two subsets , Make the sum of the elements of the two subsets equal .

First , Clarify the following four points , In fact, this problem is a 01 knapsack problem .

• The volume of the backpack is sum / 2
• The goods to be put in the backpack （ The elements in the set ） Weight is The value of the element , The value is also the value of the element
• If the backpack is just full , Indicates that the sum of sum / 2 Subset .
• Every element in the backpack can't be put repeatedly .

dp[j] Express The total capacity of the backpack is j, The maximum can be made up j The sum of the subsets of is dp[j].

This topic , It's equivalent to putting values in your backpack , So the object i The weight of is nums[i], Its value is also nums[i]. So the recurrence formula ：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]).

from dp[j] By definition , First dp[0] It must be 0. If the value given by the title is a positive integer, then it is not 0 Subscripts are initialized to 0 That's all right. , If the title gives a negative value , So no 0 The subscript is initialized to negative infinity . In this way, we can make dp The maximum value of array in the process of recursive formula , Instead of being overwritten by the initial value .

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        '''dp[j] Express   The total capacity of the backpack is j, The maximum can be made up j The sum of the subsets of is dp[j]'''
        sums = sum(nums)
        if sums % 2 == 1: return False

        dp = [0] * 10001
        target = sums // 2

        for i in range(0, len(nums)): #  Traverse the items 
            for j in range(target, nums[i] - 1, -1):  #  Traverse the backpack 
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
        
        #  The sum of the elements in the set can be made exactly target
        if dp[target] == target: 
            return True
        else:
            return False

1049. The weight of the last stone II

There is a pile of stones , Use an array of integers stones Express . among stones[i] It means the first one i The weight of a stone . Every round , Choose any two stones , Then smash them together . Suppose the weights of the stones are x and y, And x <= y. The possible results of crushing are as follows ：

• If x == y, Then both stones will be completely crushed ;
• If x != y, So the weight is x The stone will be completely crushed , And the weight is y The new weight of the stone is y-x.

Last , There's only one piece left at most stone . Return to this stone The smallest possible weight . If there is no stone left , Just go back to 0.

In fact, this problem is to divide the stones into two piles with the same weight , The smallest stone left after the collision , This is actually 01 knapsack problem .

dp[j] The capacity is j The backpack , You can recite at most dp[j] Such a heavy stone . Others are actually the same as the above question . The code is as follows ：

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total_sum = sum(stones)
        target = total_sum // 2
        dp = [0] * (target + 1)

        for i in range(len(stones)):
            for j in range(target, -1, -1):
                if j >= stones[i]:
                    dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
        
        return total_sum - dp[target] - dp[target]

494. Objectives and

Give you an array of integers nums And an integer target . Add... Before each integer in the array ‘+’ or ‘-’ , And then concatenate all the integers , You can construct a expression ：

• for example ,nums = [2, 1] , Can be in 2 Before adding ‘+’ , stay 1 Before adding ‘-’ , And then concatenate them to get the expression “+2-1”

Returns the 、 The result is equal to target Different expression Number of .

Suppose the sum of the additions is x, Then the sum corresponding to subtraction is sum - x. So what we ask is x - (sum - x) = target, solve equations , That is to say x = (S + sum) / 2. At this point, the problem turns into , The full capacity is x knapsack , There are several ways .

First , above x The solution involves division , Then we need to consider whether rounding down has any impact ：

• (S + sum) % 2 == 1： Obviously , There is no solution to this situation ！
• abs(target) > sum： There is no solution to this situation , After all, the target sum is larger than the sum of the array , How can there be a solution ？

dp[j] Express ： fill j（ Include j） Such a large volume bag , Yes dp[j] Methods .

Don't consider nums[i] Under the circumstances , The filling capacity is j - nums[i] The backpack , Yes dp[j - nums[i]] Methods . So just get nums[i] Words , manage to put together dp[j] There is dp[j - nums[i]] Methods . Then round it up dp[j] How many methods are there , That is the be-all dp[j - nums[i]] Add up .

Find the formula of combinatorial problems , It's all like this ：

dp[j] += dp[j - nums[i]]

As can be seen from the recursive formula , At initialization time dp[0] Be sure to initialize to 1, because dp[0] Is the origin of all recursive results in the formula , If dp[0] yes 0 Words , The recursive result will be 0.dp[0] = 1, It's also easy to explain in theory , The full capacity is 0 The backpack , Yes 1 Methods , It's just pretend 0 Item .

The code implementation is as follows ：

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)

        if abs(target) > total_sum: return 0
        if (target + total_sum) % 2 == 1: return 0

        bagsize = (target + total_sum) // 2

        dp = [0] * (bagsize + 1)
        dp[0] = 1  #  The full capacity is 0 The backpack , Yes 1 Methods , It's just pretend 0 Item 

        for i in range(len(nums)):
            for j in range(bagsize, nums[i] - 1, -1):
                dp[j] += dp[j - nums[i]]
        
        return dp[bagsize]

474. One and zero （🧡🧡）

Here's an array of binary strings strs And two integers m and n . Please find out and return to strs Length of the largest subset of , This subset most Yes m individual 0 and n individual 1 . If x All of the elements of are also y The elements of , aggregate x Is a collection y Of A subset of .

it is to be noted that , This question is not about multiple backpacks , In this question strs The elements in the array are items , Every item is a ！ and m and n It's like a backpack , Two dimensional backpack . Carefully understand here ！

dp[i][j]： At most i individual 0 and j individual 1 Of strs The size of the largest subset of is dp[i][j].

dp[i][j] It can be from the previous strs Derived from the string in ,strs The string in the has zeroNum individual 0,oneNum individual 1.dp[i][j] It could be dp[i - zeroNum][j - oneNum] + 1. Then we go through the process of traversal , take dp[i][j] The maximum of . So the recurrence formula ：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1).

Compare the Standards 01 Knapsack problems will be found , A string of zeroNum and oneNum Equivalent to the weight of the article （weight[i]）, The number of strings is equivalent to the value of the item （value[i]）. This is a typical 01 knapsack ！ It's just that the weight of an object has two dimensions .

The code implementation is as follows ：

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]        

        for s in strs:
            oneNum, zeroNum = s.count("1"), s.count("0")

            for i in range(m, zeroNum - 1, -1):
                for j in range(n, oneNum - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)
            
        return dp[m][n]

It can be understood as having Two dimension Of a one-dimensional array 01 knapsack problem .