Leetcode problem Solving (0-1 knapsack problem)

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

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Leetcode problem Solving (0-1 knapsack problem)

0-1 backpack problem

define

Their thinking

State definition

State transition

Code implementation

Mnemonic search

Use dynamic programming for bottom-up solution

0-1 knapsack problem optimization

Analysis of the

Two lines are used alternately to complete the knapsack problem

Continue to optimize

Code implementation

0-1 knapsack problem variant

0-1 backpack question in the interview

Leetcode 416. Split equal and subset

Analysis of the

Mnemonic search

Use bottom-up dynamic programming

Similar problems

Leetcode problem Solving (0-1 knapsack problem)

0-1 backpack problem

define

Their thinking

State definition

State transition

Code implementation

Mnemonic search

Use dynamic programming for bottom-up solution

0-1 knapsack problem optimization

Analysis of the

Two lines are used alternately to complete the knapsack problem

Continue to optimize

Code implementation

0-1 knapsack problem variant

0-1 backpack question in the interview

Leetcode 416. Split equal and subset

Analysis of the

Mnemonic search

Use bottom-up dynamic programming

Similar problems

Related Posts

【Java】 about static code block execution order, so simple a question, should everyone know?

166. Fractions to decimals

How do I use MQTT in a PHP project