Knapsack problem (01 knapsack, complete knapsack, dynamic programming)

01 knapsack problem , Two dimensional array for state design

 /**< 1th example： */
/** \brief
 *  1th solution:
 * A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
 * \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
 * \ How to purchase goods , To maximize profits , Note that at this time, there is only one item
 * \ 01 knapsack problem
 * \ analysis:
 * \    State Design :dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit ;
 * \    therefore, Can get dp State transfer equation of ：dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
 * \    The time complexity and space complexity are both O(n*m);
 * \ data :  5 8
            3 5 1 2 2
            4 5 2 1 3
 */

/**< 1th example： */
/** \brief
 *  1th solution:
 *  A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
 * \  existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
 * \  How to purchase goods , To maximize profits , Note that at this time, there is only one item 
 * \ 01 knapsack problem 
 * \ analysis:
 * \     State Design :dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit ;
 * \    therefore, Can get dp State transfer equation of ：dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
 * \     The time complexity and space complexity are both O(n*m);
 * \ data :  5 8
            3 5 1 2 2
            4 5 2 1 3
 */

/**
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int sum_size,sum_cap;
    cout << " Enter the number of items , And the capacity of the backpack ：\n";
    cin >> sum_size >> sum_cap;
    int w[sum_size+1],c[sum_size+1];
    int dp[sum_size+1][sum_cap+1];
    cout << " Enter the weight of these items ：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> w[i];
    cout << " Enter the value of these items ：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> c[i];

    for(int i=0;i<=sum_cap;++i)
        dp[0][i]=0;     //< Boundary design 
    for(int i=1;i<=sum_size;++i)
    {
        for(int v=0;v<w[i];++v)
            dp[i][v]=dp[i-1][v];// When the remaining capacity of the backpack cannot be filled i When you buy a product , You can only choose this product 
        for(int v=w[i];v<=sum_cap;++v)
        dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
    }

    int maxn=dp[sum_size][0];
    for(int i=1;i<=sum_cap;++i) //  In fact, this step should be unnecessary ,dp[sum_size][sum_cap] should 
        maxn=max(maxn,dp[sum_size][i]);//   It's a backpack   The maximum profit of the items that can be loaded ;
    cout << maxn << endl;

    cout << "debeg:\n";
    for(auto &a:dp)
    {
        for(auto b:a)
            cout << b << ' ';
        cout << endl;
    }
    cout << "OK:\n" << endl;

    int matr[sum_size+1];
    int temp=sum_cap;
    for(int i=sum_size;i>0;--i) //  Select item subscript 
    {
        if(dp[i][temp]==dp[i-1][temp])
            matr[i]=0;
        else
        {
            matr[i]=1;
            temp-=w[i];
        }
    }

    cout << "max profit: " << maxn << endl;
    cout << "choose index:\n";
    for(int i=1;i<=sum_cap;++i)
        if(matr[i]==1)
            cout << i << ' ';
    cout << endl;
    return 0;
}
*/

 

01 knapsack problem , One dimensional array for state design

/** \brief
 * 2th solution
 * A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
 * \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
 * \ How to purchase goods , To maximize profits , Note that at this time, there is only one item
 * \ 01 knapsack problem
 * \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit
 * \ therefore, Can get dp State transfer equation of ：dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i])
 * \ The time complexity and space complexity are both O(n*m)
 * \ Because of the calculation dp[i+1][] It will only be used dp[i][], And dp[i-1][] irrelevant , So we can
     Remove the first dimension , Change the state array into a one-dimensional array ;
     But use a one bit array as the status array , Is the subscript of which items cannot be found , There are pros and cons
 * \ data : 5 8
            3 5 1 2 2
            4 5 2 1 3
 */

/** \brief
 * 2th solution
 *  A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
 * \  existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
 * \  How to purchase goods , To maximize profits , Note that at this time, there is only one item 
 * \ 01 knapsack problem 
 * \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit 
 * \ therefore, Can get dp State transfer equation of ：dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i])
 * \  The time complexity and space complexity are both O(n*m)
 * \  Because of the calculation dp[i+1][] It will only be used dp[i][], And dp[i-1][] irrelevant , So we can 
      Remove the first dimension , Change the state array into a one-dimensional array ;
      But use a one bit array as the status array , Is the subscript of which items cannot be found , There are pros and cons 
 * \ data : 5 8
            3 5 1 2 2
            4 5 2 1 3
 */


//#include <iostream>
//#include <cstring>
//using namespace std;
//
//int main()
//{
//    int sum_size,sum_cap;
//    cout << " Enter the number of items , And the capacity of the backpack ：\n";
//    cin >> sum_size >> sum_cap;
//    int w[sum_size+1],c[sum_size+1];
//    int dp[sum_cap+1];
//    cout << " Enter the weight of these items ：\n";
//    for(int i=1;i<=sum_size;++i)
//        cin >> w[i];
//    cout << " Enter the value of these items ：\n";
//    for(int i=1;i<=sum_size;++i)
//        cin >> c[i];
//
//    memset(dp,0,sizeof(dp));    /**< Boundary design   */
//    for(int i=1;i<=sum_size;++i)
//    {
//        for(int v=w[i];v<=sum_cap;++v)  /**<  Error code , It should be recursion from right to left  */
//        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);   /**<  It's all about v The element on the right is irrelevant , The element on the right is used for recursion dp[i+1][] */
//    }                                       /**<  If v Recursion from left to right , It will affect the value of the elements recursed in the next column  */
//
//    int maxn=dp[0];
//    for(int i=1;i<=sum_cap;++i)
//        maxn=max(maxn,dp[i]);
//
//    cout << "error answer : " << maxn << endl;
//
//    cout << "debeg:\n";
//    for(auto &a:dp)
//        cout << a << ' ';
//    cout << endl;
//
//    for(int i=0;i<=sum_cap;++i)
//        dp[i]=0;     /**< Boundary design   */
//    for(int i=1;i<=sum_size;++i)    /**<  because dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]) */
//    {
//        for(int v=sum_cap;v>=w[i];--v)  /**<  It's all about v The element on the right is irrelevant , The element on the right is used for recursion dp[i+1][] */
//        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);/**<  If v Recursion from left to right , It will affect the value of the elements recursed in the next column  */
//    }
//
//    maxn=dp[0];
//    for(int i=1;i<=sum_cap;++i)
//        maxn=max(maxn,dp[i]);   /** but dp[sum_cap] Is it the maximum value ？ I feel like , But there is a certain doubt in my heart */
//    cout << " true answer: \n" << maxn << endl;
//
//    cout << "debeg:\n";
//    for(auto &a:dp)
//        cout << a << ' ';
//    cout << endl;
//    return 0;
//}

Complete knapsack problem , Two dimensional array for state design

/**< 2th example: */
/** \brief
 * 1th solution
 * A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
 * \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
 * \ How to purchase goods , To maximize profits , Note that there are countless pieces of each item at this time
 * \ Complete knapsack problem
 * \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit
 * \ therefore, Can get dp State transfer equation of ：dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
 * \ The time complexity and space complexity are both O(n*m)
 * \ data : 5 8
            3 5 1 2 2
            4 5 2 1 3
 */
 /**
     5 9
     3 5 1 2 2
     4 5 2 5 3
*/

/**< 2th example: */
/** \brief
 * 1th solution
 *  A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
 * \  existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
 * \  How to purchase goods , To maximize profits , Note that there are countless pieces of each item at this time 
 * \  Complete knapsack problem 
 * \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit 
 * \ therefore, Can get dp State transfer equation of ：dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
 * \  The time complexity and space complexity are both O(n*m)
 * \ data : 5 8
            3 5 1 2 2
            4 5 2 1 3
 */
 /**
     5 9
     3 5 1 2 2
     4 5 2 5 3
*/

/**
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int sum_size,sum_cap;
    cout << " Enter the number of items , And the capacity of the backpack ：\n";
    cin >> sum_size >> sum_cap;
    int w[sum_size+1],c[sum_size+1];
    int dp[sum_size+1][sum_cap+1];
    cout << " Enter the weight of these items ：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> w[i];
    cout << " Enter the value of these items ：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> c[i];

    for(int i=0;i<=sum_cap;++i)
        dp[0][i]=0;     //  Boundary design 
    for(int i=1;i<=sum_size;++i)
    {
        for(int v=0;v<w[i];++v)
            dp[i][v]=dp[i-1][v];  // When the remaining capacity of the backpack cannot be filled i When you buy a product , You can only choose this product 
        for(int v=w[i];v<=sum_cap;++v)
        dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i]);
    }

    int maxn=dp[sum_size][0];
    for(int i=1;i<=sum_cap;++i) //  In fact, this step should be unnecessary ,dp[sum_size][sum_cap] It should be a backpack 
        maxn=max(maxn,dp[sum_size][i]);//   The maximum profit of the items that can be loaded 
    cout << maxn << endl;

    cout << "debeg:\n";
    for(auto &a:dp)
    {
        for(auto b:a)
            cout << b << ' ';
        cout << endl;
    }

    int matr[sum_size+1];
    int temp=sum_cap;
    for(int i=sum_size;i>0;--i) //  Select item subscript 
    {
        if(dp[i][temp]==dp[i-1][temp])
            matr[i]=0;
        else
        {
            int num=0;
            while(dp[i][temp]-dp[i][temp-w[i]*(num+1)]==c[i]*(num+1))
            {                           //<  According to the state transfer equation ,dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
                ++num;                  //<  When dp[i][v]!=dp[i-1][v] when , Must have chosen the first i Item , But how many pieces have you chosen ,
                if(temp-w[i]*(num+1)<0) //<  from dp[i][v-w[i]] decision , When their difference equals c[i] when , Then add up one 
                    break;              //<   Keep going , Until the above conditions are not met 
            }
            matr[i]=num;
            temp-=w[i]*num;
        }

    }

    cout << "max profit: " << maxn << endl;
    cout << "choose index:\n";
    for(int i=1;i<=sum_size;++i)
        if(matr[i]!=0)
            cout << i << "th choose " << matr[i] << " pair\n" ;
    return 0;
}
*/

Complete knapsack problem , One dimensional array for state design

/**< 2th example: */
/** \brief
 * 2th solution
 * A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
 * \ existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
 * \ How to purchase goods , To maximize profits , Note that there are countless pieces of each item at this time
 * \ Complete knapsack problem
 * \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit
 * \ therefore, Can get dp State transfer equation of ：dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
 * \ The time complexity and space complexity are both O(n*m)
 * \ Because of the calculation dp[i+1][] It will only be used dp[i][], And dp[i-1][] irrelevant , So we can
     Remove the first dimension , Change the state array into a one-dimensional array
 * \ data : 5 8
            3 5 1 2 2
            4 5 2 1 3
*/

/**< 2th example: */
/** \brief
 * 2th solution
 *  A businessman with a can pack m Kg backpack goes to the countryside to buy goods ,
 * \  existing n Source of goods , And the first i There are kinds of goods wi kg , bankable pi element ,
 * \  How to purchase goods , To maximize profits , Note that there are countless pieces of each item at this time 
 * \  Complete knapsack problem 
 * \ analysis: dp[i][v] Before presentation i Items can be accommodated in a capacity of v In my backpack , Return maximum profit 
 * \ therefore, Can get dp State transfer equation of ：dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
 * \  The time complexity and space complexity are both O(n*m)
 * \  Because of the calculation dp[i+1][] It will only be used dp[i][], And dp[i-1][] irrelevant , So we can 
      Remove the first dimension , Change the state array into a one-dimensional array 
 * \ data : 5 8
            3 5 1 2 2
            4 5 2 1 3
 */


#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int sum_size,sum_cap;
    cout << " Enter the number of items , And the capacity of the backpack ：\n";
    cin >> sum_size >> sum_cap;
    int w[sum_size+1],c[sum_size+1];
    int dp[sum_cap+1];
    cout << " Enter the weight of these items ：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> w[i];
    cout << " Enter the value of these items ：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> c[i];

    memset(dp,0,sizeof(dp));    //< Boundary design 
    for(int i=1;i<=sum_size;++i)
    {
        for(int v=sum_cap;v>=w[i];--v)  //<  Error code , It should be recursion from left to right 
        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);  //< v It should be recursive from left to right , because dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
    }                                 //<  Calculation dp[i][v] The element on the left will be used , Calculate the one on the left before each calculation 

    int maxn=dp[0];
    for(int i=1;i<=sum_cap;++i)
        maxn=max(maxn,dp[i]);

    cout << "error answer : " << maxn << endl;

    cout << "debeg:\n";
    for(auto &a:dp)
        cout << a << ' ';
    cout << endl;
    cout << "OK:  \n\n";

    memset(dp,0,sizeof(dp)); //< Boundary design 
    for(int i=1;i<=sum_size;++i)
    {
        for(int v=w[i];v<=sum_cap;++v)  //< v It should be recursive from left to right , because dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);//<  Calculation dp[i][v] The element on the left will be used , Calculate the one on the left before each calculation 
    }

    maxn=dp[0];
    for(int i=1;i<=sum_cap;++i) //<  In fact, this step should be unnecessary ,dp[sum_cap] It should be a backpack 
        maxn=max(maxn,dp[i]);//<   The maximum profit of the items that can be loaded 

    cout << "true answer : " << maxn << endl;

    cout << "debeg:\n";
    for(auto &a:dp)
        cout << a << ' ';
    cout << endl;

    return 0;
}