题解 | #购物单#

//背包问题
#include <iostream>
#include <vector>

#define max(x, y) (x) > (y) ? (x) : (y)

using namespace std;

int getMax(int x, int y){
    return (x > y ? x : y);
}

int main(){
    int N = 0; //总钱数 
    int m = 0; //可购买的物品个数
    cin>>N>>m;
    //N/=10;	//都是10的整数，先除以10，减少循环次数
    
    int weight[60][3] = {0}; //价格/成本/费用 以及该件所带的附件数
    int value[60][3] = {0}; //价值（价格*重要度）
    //int dp[60][32000] = {0}; //第i个物品在j容量下可以获得的最大价值
    //int i, j;
    
    for(int i = 1; i <= m; i++){ //
        int v = 0;	//该物品价格
		int p = 0;	//该物品重要度
		int q = 0;	//该物品是主件还是附件
		cin >> v >> p >> q;
		//v/=10; //
        
        if(q == 0){ //主件
            weight[i][0] = v;
            value[i][0] = v * p;
        }
        else{ //附件(绑定主件)
            if(weight[q][1] == 0){ //第一个附件绑定的主件q
                weight[q][1] = v; //
                value[q][1] = v * p; //
            }
            else{ //第二个附件绑定的主件q
                weight[q][2] = v; //
                value[q][2] = v * p; //
            }          
        }
    }
    
    //开始遍历 DP
    vector<vector<int> > dp(m + 1, vector<int>(N+1,0));//第i个物品在j容量下可以获得的最大价值
    for(int i = 1; i <= m; i++){ //
        for(int j = 1; j <= N; j++){ //
            //假如不放入第i个物品
            dp[i][j] = dp[i - 1][j]; //一定要单独列出来
            
            //假如放入第i个物品
            if(j >= weight[i][0]){ //可以容下第i个主件时,比较放第i个或者不放第i个物品的价值
                dp[i][j] = getMax(dp[i][j], dp[i - 1][j - weight[i][0]] + value[i][0]);
            }
            if(j >= weight[i][0] + weight[i][1]){ //可以容下第i个主件和此主件的第1个附件时
                dp[i][j] = getMax(dp[i][j], dp[i - 1][j - weight[i][0] - weight[i][1]] + value[i][0] + value[i][1]);
            }
            if(j >= weight[i][0] + weight[i][2]){ //可以容下第i个主件和此主件的第2个附件时
                dp[i][j] = getMax(dp[i][j], dp[i - 1][j - weight[i][0] - weight[i][2]] + value[i][0] + value[i][2]);
            }
            if(j >= weight[i][0] + weight[i][1] + weight[i][2]){ //可以容下第i个主件和此主件的第1个附件和第2个附件时
                dp[i][j] = getMax(dp[i][j], dp[i - 1][j - weight[i][0] - weight[i][1] - weight[i][2]] + value[i][0] + value[i][1] + value[i][2]);
            }
        }
    }
    
    cout << dp[m][N]/* * 10*/ << endl;
    
    return 0;
}