The article directories

      • Complete knapsack definition
      • Question 1: The only difference between a backpack and a full backpack is in the traversal order
      • Question 2: Why do items loop in the outer layer and knapsack capacity loop in the inner layer?
      • Code template: Full knapsack problem

Complete knapsack definition

There are N items and a backpack that can carry up to W weight. The ith item’s weight is weight[I] and the resulting value is value[I]. Each item has an infinite number of items (that is, can be put into the backpack many times), and find which items to put into the backpack the sum of items is the largest.

The only difference between the full backpack problem and the 01 backpack problem is that there are an infinite number of items per item.

Similarly, there is no pure complete knapsack problem in Leetcode, but all kinds of applications that require complete knapsack need to be converted into complete knapsack problem, so I will still explain the theory and principle of pure complete knapsack problem here.

In the following explanation, I will use this example again:

The maximum weight of the backpack is 4.

Items as follows:

There’s an infinite number of each item!

What is the maximum value of items that a backpack can carry?

Question 1: The only difference between a backpack and a full backpack is in the traversal order

First, review the core code of 01 knapsack

/ / 01 knapsackfor(int i = 0; i < weight.size(); I++) {// iterate over itemsfor(int j = bagWeight; j >= weight[i]; J -) {/ / traverse the dp [j] = Max volume (dp) [j], dp [j - weight [I]] + value [I]); }}Copy the code

We know that the loop embedded in the 01 backpack is traversed from large to small, to ensure that each item is added only once. Items of a full backpack can be added multiple times, so go through them from small to large, i.e. :

// Full backpack: Walk through the items first, then walk through the backpackfor(int i = 0; i < weight.size(); I++) {// iterate over itemsfor(int j = weight[i]; j < bagWeight ; J++) {/ / traverse the dp [j] = Max volume (dp) [j], dp [j - weight [I]] + value [I]); }}Copy the code

Question 2: Why do items loop in the outer layer and knapsack capacity loop in the inner layer?

This problem is a lot of questions about here are understated and skipped, everyone default traversal items in the outer layer, traversal backpack capacity in the inner layer, as if it should be the same, so why?

Can’t you traverse the backpack capacity on the outside, traverse the items on the inside?

01 The sequence of the two for loops in the two-dimensional DP array in the backpack can be reversed. The sequence of the two for loops in the one-digit DP array must be to traverse the items first and then traverse the backpack capacity.

In a full knapsack, for a one-dimensional DP array, the nesting order of the two for loops also doesn’t matter! Because dp[j] is calculated from the corresponding dp[j] before the subscript j. Just make sure that dp[j] up to j is computed.

First to traverse the knapsack in traversal items, the code is as follows:

// Full backpack: First walk through the backpack, then walk through the itemsfor(int j = 0; j <= bagWeight; J++) {// traverses the backpack capacityfor(int i = 0; i < weight.size(); I++) {// iterate over itemsif (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
    cout << endl;
}
Copy the code

Code template: Full knapsack problem

The complete C++ test code is as follows:

// Iterate through the items first, then iterate through the backpack voidtest_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); I++) {// iterate over itemsfor(int j = weight[i]; j <= bagWeight; J++) {/ / traverse the dp [j] = Max volume (dp) [j], dp [j - weight [I]] + value [I]); } } cout <<dp[bagWeight] << endl; } int main() { test_CompletePack(); }Copy the code
// Go through the backpack first, then through the item voidtest_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    vector<int> dp(bagWeight + 1, 0);

    for(int j = 0; j <= bagWeight; J++) {// traverses the backpack capacityfor(int i = 0; i < weight.size(); I++) {// iterate over itemsif (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl; } int main() { test_CompletePack(); }Copy the code