Complete backpack and 01 Backpack

When doing dynamic programming , The feeling is particularly Abstract . Knapsack problem is a classical problem of dynamic programming , It's easy to remember formulas directly , But I always feel unable to use it flexibly , Only when the whole process is completely presented in the brain , To have a deeper understanding . Now take this opportunity to combine the classic complete backpack with 01 Backpack to make a summary .

Can be referred in advance ： The knapsack problem is super detailed - You know

knapsack problem - You know

leetcode Summary of dynamic planning introduction series _qq_42987967 The blog of -CSDN Blog

One 、01 knapsack

1. Problem definition ：

2. Transfer equation analysis

The state of this transition V[i][j] I am thinking about the meaning of 0--i When items , Capacity of j The maximum value that your backpack can carry . 

First , When the backpack capacity j<v[i] When ( That is, consider backpacking only i, however i Still can't fit ), Then this backpack can't hold anything i Of , Therefore, its greatest value is from V[i-1][j] Transferred .

otherwise ,V[i-1][j] It could be from V[i-1][j] perhaps V[i-1][j-w[i]]+w[i] The larger one of them is transferred ( The transfer equation has a greedy idea ).

Now make a table distance analysis ： Suppose there are three items , The capacity of the backpack is 14, An array of weights v{1,2,5}, Array of values w{2,3,4},

  Combined with the state table, we can better understand the meaning of the transfer equation . And we usually insert i=0 and j=0 As an initialization transition condition .

And it is easy to observe that V[i][j] stay j= After the total weight of all items , No more .

3. State compression

Considering the i The transfer equation of degree is only related to i-1 The status of times is related , Therefore, state compression can be carried out .

Two 、 Completely backpack

1. Climb stairs and Fibonacci series

Fibonacci series and climbing stairs are classic introductory questions of dynamic programming , First bring it to appetizer ：

It has a recursive formula ：

It means the k A state can be defined by k-1 The first state is followed by k-2 A state is transferred . So recursion can be used to write ：

    int climbStairs(int n) {
        if(n==1)return 1;
        if(n==2)return 2;
        return climbStairs(n-1)+climbStairs(n-2);
    }

You can also use the iterative method ：

    int climbStairs(int n) {
        if(n==1)return 1;
        if(n==2)return 2;
        int fk1=1,fk2=2,ans;
        for(int i=0;i<n-2;i++)
        {
            ans=fk1+fk2;
            fk1=fk2;
            fk2=ans;
        }
        return ans;
    }

2. Completely backpack

  It can be seen that this is related to 01 The difference between backpacks is that items can be taken for unlimited times , and 01 Backpacks can only be taken once per item .

  At first glance, this problem is quite abstract , I keep thinking about the solution of violence , And then run , Direct timeout .

3. Transfer equation analysis

  comparison 01 knapsack , The transfer equation of complete knapsack is more complicated . Again , This transfer equation can also do state compression , Please refer to knapsack problem - You know

 4. First traverse the capacity or the items

In order to combine with the problem of climbing stairs in front , Experience a process from general to abstract , The problem of climbing stairs is transformed into the description of complete knapsack problem ：

 There are two kinds of objects , The first volume is 1, The second volume is 2, The value is 1,

 The capacity of the backpack is k, Please tell me the maximum value that can be formed .

While we are climbing stairs, the practical problem is to traverse the capacity first and then the items . And only a complete backpack can traverse the capacity first and then the items , This is because the complete knapsack does not limit the number of selections .

That is to say

Recommended exercises ：

Interview questions 08.11. COINS