题解 | #购物单#

    题解：
            如果没有附件，单纯只有主件的话，就转化成0-1背包的问题；
            当有附件的时候，但是附件至多有两件，所以就分成如下
            1、选或者不选主件；
            2、选主件+ 附件A
            3、选主件+ 附件B
            4、选主件+ 附件A+附件B
            
            其中用price[] 数组来存 v[i],但是由于每个主件选的情况分多种，所以改成用二位数组来存。其中第二维表示可能选取的情况；
            再用pxw[][]表示price*weight存重要性,即0-1背包里面的 w[i];
            所以就有0-1背包问题dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
                        转化成dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i][k]]+w[i][k]); 其中 k = 0,1,2,3 表示选取主件的情况；

/*    题解：
            如果没有附件，单纯只有主件的话，就转化成0-1背包的问题；
            当有附件的时候，但是附件至多有两件，所以就分成如下
            1、只选主件；
            2、选主件+ 附件A
            3、选主件+ 附件B
            4、选主件+ 附件A+附件B
            
            其中用price[] 数组来存 v[i],但是由于每个主件选的情况分多种，所以改成用二位数组来存。其中第二维表示可能选取的情况；
            再用pxw[][]表示price*weight存重要性,即0-1背包里面的 w[i];
            所以就有0-1背包问题dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
                        转化成dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i][k]]+w[i][k]); 其中 k = 0,1,2,3 表示选取主件的情况；
*/

#include"iostream"
#include"vector"
using namespace std;
const int MAX = 66;
int main()
{
    int n , m ;
    cin>>n>>m ;
    vector<vector<int>> v(MAX,vector<int>(3,0));
    vector<vector<int>> w(MAX,vector<int>(3,0));
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    int a, b , c , d , e , f ;
    for(int i = 1; i <= m ; i++)
    {
        cin>>a>>b>>c;
        b *= a;
        if(c == 0)
            v[i][c] = a, w[i][c] = b; 
        else{
            if(v[c][1] == 0)
                v[c][1] = a, w[c][1] = b;
            else
                v[c][2] = a, w[c][2] = b;
        }
    }
    for(int i = 1 ; i <= m ; i++)
    {
        for(int j = 0; j <= n ; j++)
        {
            a = v[i][0], b = w[i][0];
            c = v[i][1], d = w[i][1];
            e = v[i][2], f = w[i][2];
            
            dp[i][j] = j >= a ? max(dp[i-1][j-a]+b,dp[i-1][j]):dp[i-1][j];
            dp[i][j] = j >= a + c ? max(dp[i-1][j-a-c]+b+d,dp[i][j]):dp[i][j];
            dp[i][j] = j >= a + e ? max(dp[i-1][j-a-e]+b+f,dp[i][j]):dp[i][j];
            dp[i][j] = j >= a + c + e ? max(dp[i-1][j-a-c-e]+b+d+f,dp[i][j]):dp[i][j];
        }
    }
    cout<<dp[m][n]<<endl;
    
    return 0;
}

/*
#include"iostream"
#include"vector"
#include"map"
#include"algorithm"
#include"string"
#include"cstring"
#include"cmath"
#include"queue"
#include"stack"
using namespace std;

int main()
{
	int n , m ;
    cin>>n>>m;
    vector<vector<int>> price(61,vector<int>(3,0));
    vector<vector<int>> pxw(61,vector<int>(3,0)); // 价格乘重要性
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));  // m见物品，总价值为n;
	int val, p, zof, w;
    for(int i = 1; i <= m ; i++)
    {
        cin>>val>>p>>zof;
        w = p*val;
        if(zof == 0) //    说明是主件
        {
            price[i][0] = val;
            pxw[i][0] = w;
        }
        else{       //    当为附件时；
            if(price[zof][1] == 0)
            {
                price[zof][1] = val;
                pxw[zof][1] = w;
            }
            else if(price[zof][2] == 0)
            {
                price[zof][2] = val;
                pxw[zof][2] = w;
            }
        }
    }
    //    分组背包问题；0-1背包的升级版，完全背包；
    for(int i = 1; i <= m ;i++)
    {
        for(int j = 0 ; j <= n; j++)
        {
            int a = price[i][0], b = pxw[i][0];
            int c = price[i][1], d = pxw[i][1];
            int e = price[i][2], f = pxw[i][2];
            
            dp[i][j] = j >= a ? max(dp[i-1][j],dp[i-1][j-a]+b): dp[i-1][j];

            dp[i][j] = j>= a+c ? max(dp[i][j],dp[i-1][j-a-c]+b+d) : dp[i][j];

            dp[i][j] = j>= a+e ? max(dp[i][j],dp[i-1][j-a-e]+b+f) : dp[i][j];

            dp[i][j] = j>= a+c+e ? max(dp[i][j],dp[i-1][j-a-c-e]+b+d+f) : dp[i][j];
        }
    }
    cout<<dp[m][n]<<endl;
	
	return 0;
} 

*/