0-1 knapsack problem (I)

List of articles

0-1 knapsack problem （ One ）

Tips ： After writing the article , Directories can be generated automatically , How to generate it, please refer to the help document on the right

---

Preface

Tips ： The following is the main body of this article , The following cases can be used for reference

One 、0-1 What is the knapsack problem ？

The knapsack problem is 「 Dynamic programming 」 It's a very classic class of problems , Knapsack problem essentially belongs to combinatorial optimization 「NP Problem completely 」. Because there are too many combinations , Therefore, the problem cannot be solved by exhaustive method , That's why 「 knapsack problem 」 Will use 「 Dynamic programming 」 To find out the root cause . Here is a simple example 0-1 knapsack problem .

Two 、 To divide into equal and subsets （Leetcode 416 secondary ）

1. Problem description

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 .

2. Description of algorithm

2.1 0-1 The basic idea of knapsack problem

0-1 Knapsack problem is essentially a dynamic programming problem , The essence of dynamic programming is to find the numerical change caused by the change of the next state and the previous state , The state transition equation ,dp[i][j] and dp[i-1][j] The relationship between .
0-1 The knapsack problem is actually the same problem ,dp[i][j]=max(dp[i-1][j],dp[i-1][jv[i]]+wight[i]), It means to traverse one item at a time , There are two options ： Take it or not , The volume of the backpack will be reduced , If you don't take it, you will keep the original state .

2.2 Analysis of specific problems

This problem can be converted to knapsack problem , Problem modeling process ： How big is the volume of the backpack 、 The quantity and value of items 、 The form of the result

1. Number of items ：nums Of size
2. The value of the goods ：nums The corresponding value
3. The volume of the backpack ： This is the difficulty of the general knapsack problem , The question here does not specify the maximum value of the backpack , At this time, we need to deform the problem ： Make the sum of the elements of the two subsets equal ==》 Sum of each subset == All elements and 1/2, Therefore, the volume of the backpack is also obvious, that is, the sum of all elements 1/2.
4. The form of the result ： First of all, we have to analyze what the result of our calculation is , The calculated value is the maximum value that can be obtained by taking this as the backpack volume , The question is whether they can be equal , Therefore, the form of the result can be transformed into ： Whether the backpack can be filled , That is, whether the maximum value is equal to the volume of the backpack .
This article only introduces the most primitive solution of knapsack problem , This is also the original form , The following articles will focus on the problem to make a variety of variants and optimization

2.4 Code display ：

class Solution {
    
public:
    bool canPartition(vector<int>& nums) {
    
        int N=nums.size();
        int sum=0;
        for(int i=0;i<N;i++)
        {
    
            sum+=nums[i];
        }
        if(sum%2!=0) return false;
        int C=sum/2;
        vector<vector<int>>dp(N,vector<int>(C+1,0));
        //  First processing 「 Consider the first item 」 The situation of 
        for (int i = 0; i <= C; i++) {
    
            dp[0][i] = i>=nums[0] ? nums[0] : 0;
        }
        //  To deal with 「 Consider the rest 」 The situation of 
        for (int i = 1; i < N; i++) {
    
            for (int j = 0; j < C + 1; j++) {
    
                //  Don't select this item 
                int n = dp[i - 1][j];
                //  Select the item , Premise 「 Residual capacity 」 Greater than or equal to 「 Volume of goods 」
                int y =j>nums[i]? dp[i - 1][j-nums[i]]+nums[i]:0; 
                dp[i][j] =max(n,y);
            }
        }
        return dp[N-1][C]==C;
}
};

summary

Tips ： Here is a summary of the article ：
Today I mainly explained 「 What is the knapsack problem 」、「 What is the essence of the knapsack problem 」 as well as 「 Why the knapsack problem needs to be solved by dynamic programming, and the knapsack problem solving routines and deformation problems are difficult , among 「01 knapsack 」 The problem is at the heart of many knapsack problems .