背包问题（01背包，完全背包，动态规划）

01背包问题，二维数组进行状态设计

 /**< 1th example： */
/** \brief
 *  1th solution:
 * 一个商人带着一个能装m千克的背包去乡下收购货物，
 * \ 现有n种货源，且第i种货物有wi千克，可获利pi元，
 * \ 如何收购商品，才能使利润最大，注意此时每样物品只有一件
 * \ 01背包问题
 * \ analysis:
 * \    状态设计:dp[i][v]表示前i件物品能够容纳在容量为v的背包里面，返回最大利润;
 * \    therefore,能得到dp的状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
 * \    时间复杂度和空间复杂度都为O(n*m);
 * \ data :  5 8
            3 5 1 2 2
            4 5 2 1 3
 */

/**< 1th example： */
/** \brief
 *  1th solution:
 * 一个商人带着一个能装m千克的背包去乡下收购货物，
 * \ 现有n种货源，且第i种货物有wi千克，可获利pi元，
 * \ 如何收购商品，才能使利润最大，注意此时每样物品只有一件
 * \ 01背包问题
 * \ analysis:
 * \    状态设计:dp[i][v]表示前i件物品能够容纳在容量为v的背包里面，返回最大利润;
 * \    therefore,能得到dp的状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
 * \    时间复杂度和空间复杂度都为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 << "输入物品的数量，以及背包的容量：\n";
    cin >> sum_size >> sum_cap;
    int w[sum_size+1],c[sum_size+1];
    int dp[sum_size+1][sum_cap+1];
    cout << "输入这些物品的重量：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> w[i];
    cout << "输入这些物品的价值：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> c[i];

    for(int i=0;i<=sum_cap;++i)
        dp[0][i]=0;     //<边界设计
    for(int i=1;i<=sum_size;++i)
    {
        for(int v=0;v<w[i];++v)
            dp[i][v]=dp[i-1][v];//当背包剩余容量装不下第i件商品时，只能不选这件商品
        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) // 其实这一步应该是不需要的，dp[sum_size][sum_cap]应该
        maxn=max(maxn,dp[sum_size][i]);//  就是背包 能装下的物品的最大利润;
    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) // 选择物品下标
    {
        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背包问题，一维数组进行状态设计

/** \brief
 * 2th solution
 * 一个商人带着一个能装m千克的背包去乡下收购货物，
 * \ 现有n种货源，且第i种货物有wi千克，可获利pi元，
 * \ 如何收购商品，才能使利润最大，注意此时每样物品只有一件
 * \ 01背包问题
 * \ analysis: dp[i][v]表示前i件物品能够容纳在容量为v的背包里面，返回最大利润
 * \ therefore,能得到dp的状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i])
 * \ 时间复杂度和空间复杂度都为O(n*m)
 * \ 由于计算dp[i+1][]只会用到dp[i][],与dp[i-1][]无关，因此我们可以将
     第一维去掉，将状态数组变成一个一维数组；
     但是用一位数组作为状态数组，是不能找到选择的哪些物品的下标，也算有利有弊吧
 * \ data : 5 8
            3 5 1 2 2
            4 5 2 1 3
 */

/** \brief
 * 2th solution
 * 一个商人带着一个能装m千克的背包去乡下收购货物，
 * \ 现有n种货源，且第i种货物有wi千克，可获利pi元，
 * \ 如何收购商品，才能使利润最大，注意此时每样物品只有一件
 * \ 01背包问题
 * \ analysis: dp[i][v]表示前i件物品能够容纳在容量为v的背包里面，返回最大利润
 * \ therefore,能得到dp的状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i])
 * \ 时间复杂度和空间复杂度都为O(n*m)
 * \ 由于计算dp[i+1][]只会用到dp[i][],与dp[i-1][]无关，因此我们可以将
     第一维去掉，将状态数组变成一个一维数组；
     但是用一位数组作为状态数组，是不能找到选择的哪些物品的下标，也算有利有弊吧
 * \ 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 << "输入物品的数量，以及背包的容量：\n";
//    cin >> sum_size >> sum_cap;
//    int w[sum_size+1],c[sum_size+1];
//    int dp[sum_cap+1];
//    cout << "输入这些物品的重量：\n";
//    for(int i=1;i<=sum_size;++i)
//        cin >> w[i];
//    cout << "输入这些物品的价值：\n";
//    for(int i=1;i<=sum_size;++i)
//        cin >> c[i];
//
//    memset(dp,0,sizeof(dp));    /**<边界设计  */
//    for(int i=1;i<=sum_size;++i)
//    {
//        for(int v=w[i];v<=sum_cap;++v)  /**< 错误代码，应该从右至左开始递推 */
//        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);   /**< 都只与v右方的元素无关，右方的元素是用来递推dp[i+1][] */
//    }                                       /**< 如果v从左至右开始递推，会对下一列递推出来的元素的值有影响 */
//
//    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;     /**<边界设计  */
//    for(int i=1;i<=sum_size;++i)    /**< 因为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)  /**< 都只与v右方的元素无关，右方的元素是用来递推dp[i+1][] */
//        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);/**< 如果v从左至右开始递推，会对下一列递推出来的元素的值有影响 */
//    }
//
//    maxn=dp[0];
//    for(int i=1;i<=sum_cap;++i)
//        maxn=max(maxn,dp[i]);   /**但dp[sum_cap]是否就是最大的值呢？我感觉是，但心中又存在着一定的疑惑*/
//    cout << " true answer: \n" << maxn << endl;
//
//    cout << "debeg:\n";
//    for(auto &a:dp)
//        cout << a << ' ';
//    cout << endl;
//    return 0;
//}

完全背包问题，二维数组进行状态设计

/**< 2th example: */
/** \brief
 * 1th solution
 * 一个商人带着一个能装m千克的背包去乡下收购货物，
 * \ 现有n种货源，且第i种货物有wi千克，可获利pi元，
 * \ 如何收购商品，才能使利润最大，注意此时每样物品有无数件
 * \ 完全背包问题
 * \ analysis: dp[i][v]表示前i件物品能够容纳在容量为v的背包里面，返回最大利润
 * \ therefore,能得到dp的状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
 * \ 时间复杂度和空间复杂度都为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
 * 一个商人带着一个能装m千克的背包去乡下收购货物，
 * \ 现有n种货源，且第i种货物有wi千克，可获利pi元，
 * \ 如何收购商品，才能使利润最大，注意此时每样物品有无数件
 * \ 完全背包问题
 * \ analysis: dp[i][v]表示前i件物品能够容纳在容量为v的背包里面，返回最大利润
 * \ therefore,能得到dp的状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
 * \ 时间复杂度和空间复杂度都为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 << "输入物品的数量，以及背包的容量：\n";
    cin >> sum_size >> sum_cap;
    int w[sum_size+1],c[sum_size+1];
    int dp[sum_size+1][sum_cap+1];
    cout << "输入这些物品的重量：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> w[i];
    cout << "输入这些物品的价值：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> c[i];

    for(int i=0;i<=sum_cap;++i)
        dp[0][i]=0;     // 边界设计
    for(int i=1;i<=sum_size;++i)
    {
        for(int v=0;v<w[i];++v)
            dp[i][v]=dp[i-1][v];  //当背包剩余容量装不下第i件商品时，只能不选这件商品
        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) // 其实这一步应该是不需要的，dp[sum_size][sum_cap]应该就是背包
        maxn=max(maxn,dp[sum_size][i]);//  能装下的物品的最大利润
    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) // 选择物品下标
    {
        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))
            {                           //< 根据状态转移方程，dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
                ++num;                  //< 当dp[i][v]!=dp[i-1][v]时，必然选择了第i件物品，但选择了多少件呢，
                if(temp-w[i]*(num+1)<0) //< 由dp[i][v-w[i]]决定，当他们的差值等于c[i]时，那么就累加一件
                    break;              //<  持续下去，直到不满足上述条件为止
            }
            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;
}
*/

完全背包问题，一维数组进行状态设计

/**< 2th example: */
/** \brief
 * 2th solution
 * 一个商人带着一个能装m千克的背包去乡下收购货物，
 * \ 现有n种货源，且第i种货物有wi千克，可获利pi元，
 * \ 如何收购商品，才能使利润最大，注意此时每样物品有无数件
 * \ 完全背包问题
 * \ analysis: dp[i][v]表示前i件物品能够容纳在容量为v的背包里面，返回最大利润
 * \ therefore,能得到dp的状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
 * \ 时间复杂度和空间复杂度都为O(n*m)
 * \ 由于计算dp[i+1][]只会用到dp[i][],与dp[i-1][]无关，因此我们可以将
     第一维去掉，将状态数组变成一个一维数组
 * \ data : 5 8
            3 5 1 2 2
            4 5 2 1 3
*/

/**< 2th example: */
/** \brief
 * 2th solution
 * 一个商人带着一个能装m千克的背包去乡下收购货物，
 * \ 现有n种货源，且第i种货物有wi千克，可获利pi元，
 * \ 如何收购商品，才能使利润最大，注意此时每样物品有无数件
 * \ 完全背包问题
 * \ analysis: dp[i][v]表示前i件物品能够容纳在容量为v的背包里面，返回最大利润
 * \ therefore,能得到dp的状态转移方程：dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
 * \ 时间复杂度和空间复杂度都为O(n*m)
 * \ 由于计算dp[i+1][]只会用到dp[i][],与dp[i-1][]无关，因此我们可以将
     第一维去掉，将状态数组变成一个一维数组
 * \ 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 << "输入物品的数量，以及背包的容量：\n";
    cin >> sum_size >> sum_cap;
    int w[sum_size+1],c[sum_size+1];
    int dp[sum_cap+1];
    cout << "输入这些物品的重量：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> w[i];
    cout << "输入这些物品的价值：\n";
    for(int i=1;i<=sum_size;++i)
        cin >> c[i];

    memset(dp,0,sizeof(dp));    //<边界设计
    for(int i=1;i<=sum_size;++i)
    {
        for(int v=sum_cap;v>=w[i];--v)  //< 错误代码，应该从左至右开始递推
        dp[v]=max(dp[v],dp[v-w[i]]+c[i]);  //< v应当是从左至右开始递推，因为dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i])
    }                                 //< 计算dp[i][v]会用到其左面的元素，每次计算都先把它左边的计算出来

    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)); //<边界设计
    for(int i=1;i<=sum_size;++i)
    {
        for(int v=w[i];v<=sum_cap;++v)  //< v应当是从左至右开始递推，因为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]);//< 计算dp[i][v]会用到其左面的元素，每次计算都先把它左边的计算出来
    }

    maxn=dp[0];
    for(int i=1;i<=sum_cap;++i) //< 其实这一步应该是不需要的，dp[sum_cap]应该就是背包
        maxn=max(maxn,dp[i]);//<  能装下的物品的最大利润

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

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

    return 0;
}