Transferred from: https://blog.csdn.net/yandaoqiusheng/article/details/84782655/ , nine lectures

1.0-1 knapsack problem

There are N items with a backpack capacity of V, each weighing w[i], and each item has a value of v[i]. There is only one item for each item. How to pack items to maximize the value of the backpack?

Definition of dp array: dp[i][j] represents the maximum value of the first I items when the backpack capacity is just j.

State transition equation:

f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+v[i])

Explanation: there are two options for the i-th item, one is to put it in the backpack, the other is not to put it in the backpack. The first item in max is not put into the backpack, so it is converted to consider putting the first i-1 items into the backpack with capacity of j; The second item is put into the backpack. The problem is that the first i-1 items are put into the backpack with the capacity of j-w[i]. At this time, the maximum value is plus the value of the current items.

1.1 space optimization

The idea of using a scrolling array:

​for (int i = 1; i <= n; i++)//Traverse items
    for (int j = V; j >= 0; j--)//ergodic capacity 
        f[j] = max(f[j], f[j - w[i]] + v[i]);

The outer layer traverses items, and the inner layer traverses from large to small, because items can only be taken once at most. (the complete knapsack problem traverses the capacity from small to large, because it can take infinite times.)

As long as the quantity is limited, it can only traverse from large to small. In fact, it is more obvious from the original formula. From large to small, it is only guaranteed to use the calculation result of i-1.

Example of force deduction: 416. Segmentation and subsets

2. Complete knapsack problem

There are a knapsack with a capacity of V and N items, each with a weight of w[i] and a value of v[i]. There are countless items for each item. How to pack items to maximize the value of the knapsack?

The meaning of dp array is the same as above. It can be written according to the quantity of each item,

f[i][j]=max(f[i−1][j−k∗w[i]]+k∗v[i])∣0<=k∗w[i]<=j

But it doesn't work.

2.1 convert to 0-1 problem

for (int i = 1; i <= n; i++)//Traverse items
    for (int j = w[i]; j <= V; j++)//ergodic capacity 
        f[j] = max(f[j], f[j - w[i]] + v[i]);

Traverse items, but the backpack capacity is from small to large, because items can be used unlimited times.

Can two-layer for loops be replaced?

give an example: 322. Change

        for(int i=1;i<=amount;i++){//If the capacity is excluded, each start means that the previous capacity has determined the final result
            for(int j=0;j<coins.size();j++){
                if(coins[j]>i)continue;
                dp[i]=min(dp[i],dp[i-coins[j]]+1);
            }
        }
        for(int i=0;i<coins.size();i++){//When coins are out, use one coin to update all capacities once at a time
            for(int j=coins[i];j<=amount;j++){
                dp[j]=min(dp[j],dp[j-coins[i]]+1);
            }
        }

2.2 initialization problems

• It is required to fill the capacity V exactly: then dp[0]=0, and the others are initialized to negative infinity, which means that only the backpack with capacity 0 may be "just filled" by nothing with value 0. The backpacks with other capacities have no legal solution and belong to undefined state.
• Not full, but optimal: then all numbers are initialized to 0, which means that the knapsack of any capacity has a legal solution "nothing", and the value of this solution is 0.

3. Multiple knapsack problem

There are multiple quantity limits for each item.

//I haven't done such a topic yet.

 

4. Mixed knapsack problem

Some can take 0-1 times, some can take infinite times, and some can take k times.

Then 0-1 and can be solved separately:

p[i]:The number of pieces of each item. 0 represents infinity
for (int i = 1; i <= n; i++)//Traverse items
    if (p[i] == 0)//Complete knapsack problem
        for (int j = w[i]; j <= V; j++)//Traversal from small to large
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    else
    for (int k = 1; k <= p[i]; k++)//If p[i]Is 1, is 0-1 Knapsack problem, otherwise it is multiple knapsack problem
        for (int j = V; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);

//I haven't done such a problem yet. I hope I can think of a solution when I do it.

5. Two dimensional cost knapsack problem

Now the goods have two weights and two values. Of course, there are also two backpacks, that is, there are two restrictions. Then add one-dimensional state:

Define the meaning of dp array: dp[i][j][k] represents the maximum value that can be achieved when considering the first I items and the backpack capacity is j and K respectively.

State transition:

max(f[i−1][j][k],f[i−1][j−w[i]][k−g[i]]+v[i])//No, no

5.1 space optimization

Then you need to traverse from large to small:

for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)//Both layers need to traverse from large to small
        for (int k = T; k >= g[i]; k--)
            f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]);

The time complexity is the product of three-tier for loops, and the space complexity is reduced to two dimensions.

Title: 474. One and zero