Record of brushing questions with force deduction -- complete knapsack problem (I)

List of articles

Complete 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 ： Here you can add the general content to be recorded in this article ：

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

One 、 Introduction to the complete knapsack problem

The complete knapsack problem is actually 0-1 Based on the knapsack problem , Added feature that each item can be selected multiple times （ Where capacity permits ）.

Two 、 Change for （Leetcode 322 secondary ）

1. Problem description

Give you an array of integers coins , Coins of different denominations ; And an integer amount , Represents the total amount . Calculate and return the amount needed to make up the total amount The minimum number of coins . If no combination of coins can make up the total amount , return -1 . You can think of the number of coins of each kind as infinite .

2. Description of algorithm

2.1 The basic idea of the complete knapsack problem

Complete knapsack problem and 0-1 The essence of knapsack problem is the same , It's just that the conditions are different . Now I will analyze it according to the code . The following code is the general method to solve the complete knapsack problem . and 0-1 The difference between the knapsack problem is ： When considering the current coin situation, you can choose multiple times , Maximum number of selections = Current backpack allowance / The face value of the current coin .

class Solution {
    
  int INF = Integer.MAX_VALUE;
  public int coinChange(int[] cs, int cnt) {
    
      int n = cs.length;
      int[][] f = new int[n + 1][cnt + 1];

      //  initialization （ There are no coins ）： Only  f[0][0] = 0; Other cases are invalid values .
      //  This is from 「 State definition 」 Decisive , When not considering any coins , You can only add up to  0  The plan , The number of coins used is  0 
      for (int i = 1; i <= cnt; i++) f[0][i] = INF;

      //  With coins 
      for (int i = 1; i <= n; i++) {
    
          int val = cs[i - 1];
          for (int j = 0; j <= cnt; j++) {
    
              //  Regardless of the current coin situation 
              f[i][j] = f[i - 1][j];

              //  Consider the current coin situation （ The current number of coins can be selected based on the current capacity ）
              for (int k = 1; k * val <= j; k++) {
    
                  if (f[i - 1][j - k * val] != INF) {
    
                      f[i][j] = Math.min(f[i][j], f[i-1][j-k*val] + k);
                  }
              }
          }
      }
      return f[n][cnt] == INF ? -1 : f[n][cnt];
  }
}

2.2 Analysis of specific problems

This problem can be transformed into a complete 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 ： Backpack size
4. Initial value ： This is also the difficulty of many knapsack problems , The so-called initial value here , does dp[0]、dp[1]…dp[n] The meaning of representation . If you want to determine the initial value, you should determine which values are invalid according to the meaning of the topic , Which values need to be transferred .
5. The form of the result ： The problem of the topic is how to calculate and return the minimum number of coins needed to make up the total amount . The original solution of knapsack problem is to find the solution with the greatest value . But now we need to be flexible , In essence, it is still analyzing the state transition equation . Namely dp[j] and dp[j - v[i]] The relationship between , Here is the coin , The last thing I want is that the minimum number of coins is not the maximum value , therefore dp[j] and dp[j - v[i]] Namely dp[j]=min（dp[j],dp[j - v[i]]+1);
6. The final result is ： You need to judge which values are valid values according to the initial values , Which are invalid values .

2.4 Code display ：

class Solution {
    
private:
    int INF = 0x3f3f3f3f;
public:
    int coinChange(vector<int>& coins, int amount) {
    
        int C=coins.size();
        vector<int> dp(amount+1,INF);
        dp[0]=0;
        if(amount==0) return 0;
        for(int i=0;i<C;i++)
        {
    
            for(int j=coins[i];j<=amount;j++)
            {
    
                int yes=dp[j-coins[i]]+1;
                dp[j]=min(dp[j],yes);
            }
        }
        return dp[amount]==INF?-1:dp[amount];
    }
};

summary

Tips ： Here is a summary of the article ：

for example ： That's what we're going to talk about today , This article only briefly introduces 「 What is the complete knapsack problem 」、「 What is the essence of the knapsack problem 」 as well as 「 Why is the conventional solution of complete knapsack problem and the difficulty of solving routine and deformation problems of complete knapsack , More will be introduced later according to the examples .