knapsack problem (Knapsack problem) It's a kind of combinatorial optimization NP (NP-Complete) Problem completely .
Given a set of items , Each item has its own weight and price , Within the total weight limit , How to choose , To maximize the total price of the item . The name of the problem comes from how to choose the most suitable item to put in a given backpack .

General questions ： Yes n Items and a capacity (capacity) by C The backpack , Note No i The weight of an item (weight) by $w_i$, value (value) by $v_i$, Ask which items can be loaded into the backpack to maximize the total value .

0-1 knapsack ： If you limit each item to a maximum of 1 Time , The problem is called 0-1 knapsack problem .

Completely backpack ： If each item can be selected an unlimited number of times , The problem is called Complete knapsack problem .

Suppose the items put in the backpack i The number is $k_i$, Then the above knapsack problem can be expressed mathematically as ：

$\max {\sum }_{i=0}^{n-1}{k}_i\cdot v_i$

$$\sum _{i=0}^{n-1}{k}_i\cdot w_i⩽C,\{\begin{array}{l}{k}_i\in \{0,1\}*「0-1knapsack\; problem」\\ k_i\in \{0,1,2,...,+\infty \}*「Complete\; knapsack\; problem」\end{array}$$

416. To divide into equal and subsets

Title Review ： Given an array of integers nums And an integer target, Add... Before each integer in the array + or -, Construct an addition and subtraction expression , Make the result equal to targettarget, Ask how many construction methods ？

Here are two general methods to solve this kind of problem ：

Method 1 ： Memory search
Method 2 ： Dynamic programming
expand ：

Master the template , Can solve a crowd 「0-1 knapsack problem 」：

Question no Answer key difficulty
416. To divide into equal and subsets Memory search 、 Dynamic programming + Space optimization secondary
474. One and zero Memory search 、 Dynamic programming + Space optimization secondary
（ This topic ）494. Objectives and Memory search 、 Dynamic programming + Space optimization secondary
（ Similar topics ） The finger of the sword Offer II 102. The target value of addition and subtraction Memory search 、 Dynamic programming + Space optimization secondary
（ Close to this topic ） 1049. The weight of the last stone II Memory search 、 Dynamic programming + Space optimization secondary

Yes 「0-1 knapsack 」 The template is slightly expanded , It can be used to solve a crowd 「 Complete knapsack problem 」：

Question no Answer key difficulty
322. Change for from 0-1 Backpack to full backpack , Go deep layer by layer + deduction secondary
518. Change for II from 0-1 Backpack to full backpack , Go deep layer by layer + Mathematical derivation secondary
279. Complete square Explain the complete backpack （ Including mathematical derivation ） secondary
Method 1 ： Memory search

Recursively searching ： Regular recursive search dfs(i,\ *args)dfs(i, ∗args) After reaching a position ii There are only two situations （ Choose or not ）：

skip ii Location ： Think directly about the next step ;
choice ii Location ： Judge whether the choice is feasible according to the actual situation , And choice ii How to proceed in the next step .
This question is for ii Location elements , Add a plus sign to it + Or the minus sign -, Analogous to choosing or not choosing no ii Elements in position .

Recursive search is essentially a violent solution , Time complexity is usually at the exponential level , Obviously, it is not a good implementation method when the amount of data is large .

After adding memorization to the search , The corresponding code is as follows ：

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        
        cache = {
    }      #  Memory unit 
        
        # @functools.cache # Python functools Self contained memory unit 【 After enabling, customization can be omitted cache unit 】
        def dfs(i, summ, t):
            '''summ:  front i The sum of expressions of elements ; t:  The target '''
            if (i, summ) in cache:          #  Memorize ： Already exists , Go straight back to 
                return cache[(i, summ)]

            if i == len(nums):              #  Traverse all elements , Recursion aborts 
                if summ == t:               #  Found a combination that meets the requirements 
                    cache[(i, summ)] = 1
                else:
                    cache[(i, summ)] = 0
                return cache[(i, summ)]
            
            pos_cnt = dfs(i+1, summ + nums[i], t)       # nums[i] Add '+' Number 
            neg_cnt = dfs(i+1, summ - nums[i], t)       # nums[i] Add '-' Number 
            cache[(i, summ)] = pos_cnt + neg_cnt        #  The sum of the combination numbers of the above two cases 
            return cache[(i, summ)]
        
        return dfs(0, 0, target)
 

The time complexity of the above algorithm is close O(2^n),\ n=len(nums)O(2
n
), n=len(nums), So it's not suitable for nums There are many elements in .

Many top-down recursive search processes can be modified into lower complexity bottom-up dynamic planning processes , Now let's introduce the implementation method of Dynamic Planning .

Method 2 ： Dynamic programming

Topic analysis ：

Remember that the sum of the elements of the array is total, add to + The sum of the elements of the number is pos, add to - The sum of the elements of the number is neg, It has the following relationship ：

\begin{cases} pos + neg = total \ pos - neg = target \end{cases}
{
pos+neg=total
pos−neg=target
​

Further, we can get ：

\begin{cases} pos = (total + target) / 2 \ neg = (total - target) / 2 \end{cases}
{
pos=(total+target)/2
neg=(total−target)/2
​

Problem transformation ：
It's not hard to find , This question is essentially a 「0-1 knapsack problem 」： Given a non empty array containing only positive integers numsnums, Determine whether you can select some numbers from the array （ Each element can be selected at most once ）, Make the sum of these selected numbers exactly equal pospos perhaps negneg.

You can judge before executing the program numsnums Whether some basic conditions are met , Such as total>targettotal>target、total+targettotal+target Can be 22 Division, etc , If the program is not satisfied, you can return directly 00.

「0-1 knapsack problem 」 General form ：
Dynamic programming is to solve 「0−1 knapsack problem 」 Standard practice of . In a general way , We define ：dp[i][j]dp[i][j] Before presentation ii Put one item into a container with a capacity of jj The maximum value that you can get from your backpack , Then the state transition process can be expressed as ：

No choice ii Item ： The problem turns to the former i-1i−1 The capacity of items is jj The value gained in the backpack ：dp[i][j] =dp[i-1][j]dp[i][j]=dp[i−1][j] ;
Select the first ii Item ： The first ii Items occupy capacity w_iw
i
​
, front i-1i−1 Put items into the remaining capacity of j-w_ij−w
i
​
In my backpack , The problem turns to the former i-1i−1 The capacity of items is j-w_ij−w
i
​
The value gained in the backpack dp[i-1][j-w_i]dp[i−1][j−w
i
​
] Add the number to be put ii The value of items v_iv
i
​
：dp[i][j] =dp[i-1][j-w_i] + v_idp[i][j]=dp[i−1][j−w
i
​
]+v
i
​
. Be careful , It can be put into No ii The premise of this article is ：w_i \leq jw
i
​
≤j.
The greater of the two cases ：

dp[i][j] = \max\left{ \ dp[i-1][j],\quad dp[i-1][j-w_i] + v_i \ \right}\ .\quad \quad \quad （1）
dp[i][j]=max{ dp[i−1][j],dp[i−1][j−w
i
​
]+v
i
​
} .（1）

️ In the knapsack problem of finding the optimal solution , Some problems require the optimal solution when the backpack is just full , Some problems require the optimal solution when the backpack capacity is not exceeded . One difference between these two methods is that the implementation method is different when the state is initialized .[ Excerpt from @《 Knapsack question 9 》（ Web version ） （PDF edition ）]
The initialization of the dpdp Array is actually the legal state when there is no item in the backpack ：

If it is required to fill the backpack exactly , Then during initialization dp[i][0]=0dp[i][0]=0, Other dp[i][1,2,…,]dp[i][1,2,…,∗] All set to -∞−∞. This is because at this time, only the capacity is 00 The backpack may be worth 00 Of nothing “ It happens to be full of ”, There is no legal solution for other backpacks , Belonging to an undefined state .
If you just ask not to exceed the capacity of the backpack and make the value of the items in the backpack as large as possible , When initializing dp[][*]dp[∗][∗] All set to 00. This is because it corresponds to any backpack , There is a legal solution for “ Nothing ”, Value is 00.

Analysis of this topic ：

For this question ,nums[i]nums[i] It corresponds to... In the conventional knapsack problem ii The weight of an item . What we need to do is from the array numsnums Choose a number from the list （ Each element can be selected at most once ） Make the sum just equal to pospos perhaps negneg, And calculate how many different options there are .

I. State definition

\ \quad For this question , Definition dp[i][j]dp[i][j] Express ： Once upon a time ii Choose a number from the numbers , Make the sum of the selected numbers jj Number of programmes .

II. State shift

\ \quad According to the requirements of this question , Above 「0-1 knapsack problem 」 State transfer equation of （1） Can be modified to ：

dp[i][j] = dp[i-1][j] \ + \ dp[i-1][j-nums[i]] \ . \quad \quad \quad \quad （2）
dp[i][j]=dp[i−1][j] + dp[i−1][j−nums[i]] .（2）

III. initialization

\ \quad Memory array nums The length of is nn. For the convenience of status update , Reduce the judgment of boundaries , Initial two-dimensional dpdp The array dimension is {(n+1) \times (*)}(n+1)×(∗), The first dimension is n+1n+1 Also means that ： The first ii Numbers are nums[i-1]nums[i−1], The first 11 Numbers are nums[0]nums[0], The first 00 Numbers are empty .

On initialization ：

dp[0][0] = 1dp[0][0]=1： It means before 00 Select several numbers from the numbers so that the sum is 00 The number of schemes is 11, namely 「 Empty set 」 Don't choose any number to get 00.
For others dp[0][j],\ \ j\geq 1dp[0][j], j≥1, Then there are dp[0][j] = 0dp[0][j]=0：「 Empty set 」 No number can be chosen to make its sum j\geq 1j≥1.
dp[i][0] = 1dp[i][0]=1 It has been embodied in the iterative implementation of the program , There is no need to repeat the definition in advance .

Code

1. 【 A two-dimensional DP】 The basic code of dynamic planning is as follows ：

Python3

class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
‘’’ pos + neg = total ‘’’
‘’’ pos - neg = target ‘’’
total = sum(nums)
if abs(target) > total: # target May be a negative
return 0
if (total + target) % 2 == 1: # Can not be 2 to be divisible by 【 Corresponding to pos Is not an integer 】
return 0

    '''【0/1 knapsack 】： from nums Choose a number from the list to form pos or neg'''
    pos = (total + target) // 2
    neg = (total - target) // 2
    capcity = min(pos, neg)         #  take pos and neg The smaller of them , So that dp The smallest space 
    n = len(nums)

    #  initialization 
    dp = [[0] * (capcity+1) for _ in range(n+1)]
    # dp[i][j]:  Once upon a time i Select several of the elements, and their sum is j Number of alternatives 
    dp[0][0] = 1        #  other  dp[0][j] Are all 0

    #  Status update 
    for i in range(1, n+1):
        for j in range(capcity+1):
            if j < nums[i-1]:       #  Limited capacity , Cannot select the i A digital nums[i-1]
                dp[i][j] = dp[i-1][j]
            else:                   #  You can choose the i A digital nums[i-1], No choice 【 The sum of the two methods 】
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
    
    return dp[n][capcity]

Complexity analysis

Time complexity ：O(n×capcity)O(n×capcity), among nn Is the length of the array ,capcitycapcity yes pospos and negneg The smaller of them .

Spatial complexity ：O(n×capcity)O(n×capcity).

2. 【 A one-dimensional DP】 The optimization of dynamic programming rolling array is as follows ：

In the above state transition equation , In every line dpdp The status values are only the same as those in the previous line dpdp The status value is related , Therefore, the state space can be adjusted based on the idea of rolling array dpdp Optimize without the first dimension ：

\textcolor{red}{dp2[j]}=dp[j] + dp[j−nums[i-1]]\ .
dp2[j]=dp[j]+dp[j−nums[i−1]] .

Python3Python3

class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
‘’’ pos + neg = total ‘’’
‘’’ pos - neg = target ‘’’
total = sum(nums)
if abs(target) > total: # target May be a negative
return 0
if (total + target) % 2 == 1: # Can not be 2 to be divisible by 【 Corresponding to pos Is not an integer 】
return 0

    '''【0/1 knapsack 】： from nums Choose a number from the list to form pos or neg'''
    pos = (total + target) // 2
    neg = (total - target) // 2
    capcity = min(pos, neg)         #  take pos and neg The smaller of them , So that dp The smallest space 
    n = len(nums)

    #  initialization 
    dp = [0] * (capcity+1)
    dp[0] = 1

    #  Status update 
    for i in range(1, n+1):
        dp2 = [0] * (capcity+1)     #  Scrolling array 
        for j in range(capcity+1):
            if j < nums[i-1]:       #  Limited capacity , Cannot select the i A digital nums[i-1]
                dp2[j] = dp[j]
            else:                   #  You can choose the i A digital nums[i-1], No choice 【 The sum of the two methods 】
                dp2[j] = dp[j] + dp[j-nums[i-1]]
        dp = dp2
    
    return dp[capcity]

Complexity analysis

Time complexity ：O(n×capcity)O(n×capcity), among nn Is the length of the array ,capcitycapcity yes pospos and negneg The smaller of them .

Spatial complexity ：O(capcity)O(capcity).

3. 【 A one-dimensional DP】 Reverse order of inner circulation ：

In the process of state transition , In every line dpdp The status values are only related to the status values directly above and above the left , Therefore, the state space dpdp Further optimization without scrolling arrays dp2dp2：

\textcolor{red}{dp[j]}=dp[j]\ +\ dp[j−nums[i-1]] \ .
dp[j]=dp[j] + dp[j−nums[i−1]] .

Considering me, we are updating dp[j]dp[j] when , In fact, it uses the previous line dpdp value ; And if the second level cycle is calculated from small to large , that dp[j−nums[i-1]]dp[j−nums[i−1]] Precede dp[j]dp[j] Be updated , So when we calculate dp[j]dp[j] When it's worth it ,dp[j−nums[i-1]]dp[j−nums[i−1]] It has been updated , Instead of the previous line dpdp The value of .

And in the second cycle , By calculating in reverse order from large to small, we can skillfully ensure that in the calculation dp[j]dp[j] Used in dp[j]dp[j] and dp[j-nums[i-1]]dp[j−nums[i−1]] All from the previous line .

Python3

class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
‘’’ pos + neg = total ‘’’
‘’’ pos - neg = target ‘’’
total = sum(nums)
if abs(target) > total: # target May be a negative
return 0
if (total + target) % 2 == 1: # Can not be 2 to be divisible by 【 Corresponding to pos Is not an integer 】
return 0

    '''【0/1 knapsack 】： from nums Choose a number from the list to form pos or neg'''
    pos = (total + target) // 2
    neg = (total - target) // 2
    capcity = min(pos, neg)         #  take pos and neg The smaller of them , So that dp The smallest space 

    #  initialization 
    dp = [0] * (capcity+1)
    dp[0] = 1

    #  Status update 
    for num in nums:
        for j in range(capcity, num-1, -1): #  Reverse order of inner circulation , And j>=num 【j<num There is no need to update dp[j]】
            dp[j] += dp[j-num]              #  You can select the current number num, No choice 【 The sum of the two methods 】
    
    return dp[capcity]

Complexity analysis

Time complexity ：O(n×capcity)O(n×capcity), among nn Is the length of the array ,capcitycapcity yes pospos and negneg The smaller of them .

Spatial complexity ：O(capcity)O(capcity).

Next ： It is translated into 【0-1 knapsack 】 The idea of the problem
The copyright belongs to the author
3
comments

Hottest

edit
preview

Comment on

Flying sky
L3
2022-05-04
I really like the solutions of this series , It's very good.

1
Step on
reply

XP597
2022-07-04
have a lucid brain 、 Well organized , That's great ！

Fabulous
Step on
reply

yellow0523
2022-06-23
Well said , Why no one commented ？？？

Fabulous
Step on
reply

Steve