This paper mainly introduces 0-1 knapsack problem and some leetcode problem solutions

0-1 backpack problem

define

There is a backpack, its Capacity is C. Now there are different items in n, numbered 0… N-1, where each item has a weight of W (I) and a value of V (I). Ask what items can be placed in the backpack to maximize the total value of items within the backpack’s capacity.

Their thinking

These are all combinatorial problems that we can do recursively. It is just whether we can find overlapping subproblems, optimal substructures and then transform into memory search or dynamic programming to solve.

We have two constraints on this problem

  • First we have to choose between n objects
  • The second point is that its capacity is less than or equal to a given number C.

State definition

Note that this problem uses two variables to define the state.

F(n,C) considers putting n items into a backpack of capacity C to maximize value.

State transition

For F(I,c), there are two cases: add the ith item and ignore the ith item

F(i,C) = max{F(i-1, C), v(i) + F(i-1, C-w(i))}
Copy the code

Code implementation

Mnemonic search


    class Knapsack01{
    
    private:
        vector<vector<int>> memo;
    
        // Fill the maximum value of the backpack with volume C with the item [0...index]
        int bestValue(const vector<int> &w, const vector<int> v, int index, int c){
    
            if( c <= 0 || index < 0 ) {
                return 0;
            }
    
            if( memo[index][c] ! =- 1 ) {
                return memo[index][c];
            }
    
            int res = bestValue(w, v, index- 1, c);
            if( c >= w[index] ) {
                res = max( res , v[index] + bestValue(w, v, index- 1, c-w[index]) );
            }
    
            memo[index][c] = res;
            return res;
        }
    public:
        int knapsack01(const vector<int> &w, const vector<int> &v, int C){
    
            assert( w.size() == v.size() && C >= 0 );
            int n = w.size();
            if( n == 0 || C == 0 )
                return 0;
    
            memo = vector<vector<int>>( n, vector<int>(C+1.- 1));
            return bestValue(w, v, n- 1, C); }};Copy the code

Use dynamic programming for bottom-up solution

So in simulation, each position is determined by two positions


    class Knapsack01{
    
    public:
        // Fill the maximum value of the backpack with volume C with the item [0...index]
        int knapsack01(const vector<int> &w, const vector<int> &v, int C){
    
            assert( w.size() == v.size() && C >= 0 );
    
            if ( n == 0) {
                return 0;
            }
    
            int n = w.size();
            vector<vector<int>> memo( n, vector<int>(C+1.0));
    
            for ( int j = 0; j <= C; j++ ) {
                memo[0][j] = ( j >= w[0]? v[0] : 0 );
            }
    
            for ( int i = 1; i < n; i++ ) {
                for ( int j = 0; j <= C; j++ ) {
                    // 0~ I The maximum value of these items for knapsack with volume j
                    memo[i][j] = memo[i- 1][j];
                    if( j >= w[i] ) {
                        memo[i][j] = max( memo[i][j], v[i] + memo[i- 1][j-w[i]]); }}}return memo[n- 1][C]; }};Copy the code

0-1 knapsack problem optimization

Analysis of the

The 0-1 knapsack problem above has time complexity: O(nC), space complexity: O(nC).

Let’s analyze the state transition equation: F(I,C) = Max {F(i-1, C), v(I) + F(i-1, c-w (I))} the i-th element only depends on the i-th element. In theory, you only need to keep two rows of elements. Space complexity: O(2*C)=O(C).

Two lines are used alternately to complete the knapsack problem

    
    class Knapsack01{
    
    public:
        int knapsack01(const vector<int> &w, const vector<int> &v, int C){
            assert( w.size() == v.size() && C >= 0 );
            int n = w.size();
            if( n == 0 && C == 0 )
                return 0;
    
            vector<vector<int>> memo( 2.vector<int>(C+1.0));
    
            for( int j = 0 ; j <= C ; j ++ )
                memo[0][j] = ( j >= w[0]? v[0] : 0 );
    
            for( int i = 1 ; i < n ; i ++ )
                for( int j = 0 ; j <= C ; j ++ ){
                    memo[i%2][j] = memo[(i- 1) %2][j];
                    if( j >= w[i] )
                        memo[i%2][j] = max( memo[i%2][j], v[i] + memo[(i- 1) %2][j-w[i]]);
                }
            return memo[(n- 1) %2][C]; }};Copy the code

Continue to optimize

The knapping problem is complicated with just one line: We refresh the content from right to left

Code implementation


    class Knapsack01{
    
    public:
        int knapsack01(const vector<int> &w, const vector<int> &v, int C){
            assert( w.size() == v.size() && C >= 0 );
            int n = w.size();
            if( n == 0 || C == 0 )
                return 0;
    
            vector<int> memo(C+1.0);
    
            for( int j = 0 ; j <= C ; j ++ )
                memo[j] = ( j >= w[0]? v[0] : 0 );
    
            for( int i = 1 ; i < n ; i ++ )
                for( int j = C ; j >= w[i] ; j -- )
                    memo[j] = max( memo[j], v[i] + memo[j-w[i]]);
    
            returnmemo[C]; }};Copy the code

0-1 knapsack problem variant

  • Multiple knapsack problem: There are num(I) instead of 1 per item
  • Full backpack problem: Each item can be used indefinitely
  • Multidimensional backpack problem: Consider the volume and weight of items in two dimensions
  • Add more constraints between items: Items can be mutually exclusive; They can be interdependent

0-1 backpack question in the interview

Leetcode 416. Split equal and subset

Analysis of the

Typical backpack problem, pick a certain item out of n items and fill sum/2’s backpack.

Mnemonic search

    
    class Solution {
    private:
        // Memo [I][c] indicates whether a backpack of size C can be completely filled with these elements indexed by [0... I]
        // -1 is not calculated; 0 indicates that it cannot be filled. 1 indicates that it can be filled
        vector<vector<int>> memo;
    
        // Nums [0...index] can be used to completely fill a backpack with a capacity of sum
        bool tryPartition(const vector<int> &nums, int index, int sum){
    
            if( sum == 0 ) {
                return true;
            }
    
            if( sum < 0 || index < 0 ) {
                return false;
    
            }
    
            if( memo[index][sum] ! =- 1 ) {
                return memo[index][sum] == 1;
            }
    
            memo[index][sum] = (tryPartition(nums, index- 1 , sum ) ||
                                tryPartition(nums, index- 1 , sum - nums[index] ) ) ? 1 : 0;
    
            return memo[index][sum] == 1;
        }
    public:
        bool canPartition(vector<int>& nums) {
    
            int sum = 0;
            for( int i = 0 ; i < nums.size() ; i ++ ){
                assert( nums[i] > 0 );
                sum += nums[i];
            }
    
            if( sum%2 ) {
                return false;
            }
    
            memo = vector<vector<int>>(nums.size(), vector<int>(sum/2+1.- 1));
            return tryPartition(nums, nums.size()- 1 , sum/2); }};Copy the code

Use bottom-up dynamic programming

    
    class Solution {
    
    public:
        bool canPartition(vector<int>& nums) {
    
            int sum = 0;
            for( int i = 0 ; i < nums.size() ; i ++ ){
                assert( nums[i] > 0 );
                sum += nums[i];
            }
    
            if( sum%2 ) {
                return false;
            }
    
            int n = nums.size();
            int C = sum / 2;
            vector<bool> memo(C+1.false);
    
            for ( int i = 0; i <= C; i++ ) {
                memo[i] = ( nums[0] == i );
            }
    
            for ( int i = 1; i < n; i++ ) {
                for ( intj = C; j >= nums[i]; j-- ) { memo[j] = memo[j] || memo[ j - nums[i] ]; }}returnmemo[C]; }};Copy the code

Similar problems

  • leetcode 322
  • leetcode 377
  • leetcode 474
  • leetcode 139
  • leetcode 494

— — — — — — — — — — — — — — — — — — — — — — — — — gorgeous line — — — — — — — — — — — — — — — — — — — —

After watching the friends can click a like/follow, your support is the biggest encouragement to me.

Personal blog tomato technology small stack and gold digging home page

If you want to know more, please follow my wechat official account: Tomato Technology Xiaozhan