How to consider the arrangement of complete knapsack

The permutation problem under complete knapsack

Title source :( Power button 377)

https://leetcode.cn/problems/combination-sum-iv/

stem :

Here you are Different An array of integers nums , And a target integer target . Please start from nums Find and return the sum of target The number of element combinations of .

The data of the questions ensure that the answers are in line with 32 Bit integer range .

Example 1：

Input ：nums = [1,2,3], target = 4
Output ：7
explain ：
All possible combinations are ：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Please note that , Different sequences are considered as different combinations .
Example 2：

Input ：nums = [9], target = 3
Output ：0

---

Regular full backpacks

To put it bluntly, what is a complete backpack : There are a lot of things , Each item has its own value and weight , Now I have a backpack with a maximum volume weight , Let you go to the pile of items to choose clothes , How can you pretend to be the most valuable ? If each item can only be used once , That's typical 0-1 knapsack problem , And if every item can be used countless times , That would turn into a complete knapsack problem

0-1 What about the backpack ?

Usually maintain a two-dimensional array dp [ i ] [ j ] : Meaning is : front i Characters , The current backpack capacity is j Under the circumstances , The greatest value you can get is dp [ i ] [ j ]

That's the basis dp Definition of array , We can easily get the recurrence formula :

//1. If the lower part of the current back package :
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]+value[i]])// Pay attention to what you want to use i Is it a subscript or just 1 Represents the first item , So pay attention to the details 
//2. If the current backpack can't fit at all , namely j<weight[i]
dp[i][j] = dp[i-1][j]

But the general question will ask us to return to one dp [n] [target],n Is to give the length of an array , That is to say, the whole array is considered as an object ,target Express a purpose , For example, can we wait and divide a subset ,target Is the sum and division of all elements 2 obtain , If you can select some elements from the given array to fill the capacity of target The backpack , The title can be returned to true Slightly , Many topics are 0-1 The abstraction of backpacks . But the idea is almost the same .

however 0-1 Backpack I think the most important thing to pay attention to : It's two layers for In the order of loop traversal , Sometimes it is to carry things before carrying them , Sometimes it can only be reversed , Sometimes you can , Then I found : Only the recursive formula you expect depends on [i-1] Such previous data , It is usually the first thing to do and then the backpack , Because when filling a two-dimensional array line by line , You need to get the data in the upper left corner first to figure out what to fill in the current position . For example, the problem of changing change , To solve the knapsack problem , The capacity of the backpack is the amount of money you want to change , The item to be selected is the array , If each denomination of money can only have one time 0-1 knapsack , The opposite is the complete knapsack problem . Then fill in the current position , List all the data you have calculated before that it can rely on , And rely on them to give you the value of your current position , So I think the local exhaustion is the key to the recurrence formula , Of course, this is just a personal summary , You can try this thinking when you brush questions , How can I fully consider how much data has been calculated to push to the current position ? this is it

A two-dimensional dp table It can be optimized to one dimension

If the recursive formula shows that the data of the current position is only related to the data in its adjacent cells , Then the probability can be compressed , How to compress ? Actually, it's a double layer for The traversal order of the loop has given us the answer , For example, first traverse i( That's ok ) Re traversal j( Column ), In other words, you are currently filling in No i OK, No j Columns of data :dp[i] [j], For example, the recursive formula takes the one above as an example , In fact, you have an outer layer for Cycle to the j Column data and your current i Layer traversed to the j The column data are all on the same layer, right , If you say i This dimension is flattened , If you take one dp[j], Do nothing , In fact, you got the two-dimensional array dp[i-1] [j] The data of , therefore :

dp[j] = Math.max(dp[j],dp[j-weight[i]+value[i]])

At this point, you will successfully optimize the space complexity ~

Of course, if it's an inverted traversal , And the current position is related to the data of the three positions that have been calculated , You may also need to match certain variables to record certain data , Because you don't record , It will be covered , Then you will never get it again , For example, you can try how to compress the space of the longest palindrome subsequence , No more details here

Is there anything to pay attention to when optimizing to one dimension ?

I just said , It is optimized to be one-dimensional because it needs to use old data , So if you're inside for If the loop is traversed in positive order , It will directly cover the old data , Then you want to use the old data in your future position , You won't get it , So at this time, the inner layer for The loop becomes a flashback traversal , It is precisely because a position in a two-dimensional array will not be modified after it is filled , So inside you for Loops are OK even if they are positive traversal .

Say so much why ?

Because if this question is only in 0-1 On the basis of backpack, if items can be reused , At most, adding a selected item to the selection list in the code mentioned above can complete item reuse .

But I don't know if you've noticed , If you traverse the items first and then the backpack , Actually : Let's assume that there are two objects :1,2 Represents the weight of the first and second item respectively ( It's also value )

Then go through the items first and then the backpack : Every backpack must be first 1 after 2, Instead of first 2 after 1 The situation of , That explains it :

The traversal sequence from items to backpacks will bring us the result of combination

On the contrary ?

First backpack and then items , For example, we can consider several options for a full package , Let the capacity be 3, There are items 1,2

Then the full package will contain 1,2 and 2,1, Although the item is still these two items , But it counts as two different results , therefore :

The traversal sequence of backpacks first and then items brings us the result of arrangement

---

Back to this question , How to write ? Because after the above analysis , We know that the problem is to find the permutation , And the backpack capacity is target, And it is a complete knapsack problem .

If we define dp[i] [j] Before i Array elements , Can have the most dp[i] [j] The scheme consists of j

that :

// The recurrence formula is :dp[i][j] = dp[i-1][j] + dp[i][j-1]

But is this really right ? The answer is No .

At this point we should define dp[i] [j] : The combined length is i All of our plans , How many of them can make up j

therefore

So you can go directly to the code :

class Solution {
    
    public int combinationSum4(int[] nums, int target) {
    
        //dp[i][j] It is defined that the combined length is i How many of all the solutions can be made up of j
        int[][] dp = new int[target+1][target+1];// Want to go back dp[target][target]
        dp[0][0] = 1;
        int ans = 0;
        for(int i =1;i<=target;i++){
    
            for(int j = 0; j<=target;j++){
    
                for(int tmp:nums){
    
                    if(j>=tmp) dp[i][j] +=dp[i-1][j-tmp];
                }
            }
            ans+=dp[i][target];
        }
        return ans;
    }
}

The above code can consider 1,2 and 2,1 Different , Both can contribute to the results .

Consider how to optimize to one dimension :

Consideration should be given to... For each backpack capacity :1,2 and 2,1 As a different combination

class Solution {
    
    public int combinationSum4(int[] nums, int target) {
    
        //int n = nums.length;
        //dp[i][j] It is defined that the combined length is i How many of all the solutions can be made up of j
        int[] dp = new int[target+1];// Want to go back dp[target]
        dp[0] = 1;
        for(int i =1;i<=target;i++){
    
            for(int tmp:nums){
    
                if(i>=tmp) dp[i]+=dp[i-tmp];
            }
        }
        return dp[target];
    }
}