C++-购物单

1、主要思路是把这个问题简化为1-0背包问题，其中是附件的物品，不作为单独的一个物品；只有当遇到包含附件的主物品时，才对包含的附件一块进行判断。

2、首先把输入进行保存，第0维表示物品价格，第1维表示物品的满意度，第2维表示是否为附件，如果判断出当前物品是附件，就把当前物品坐标保存到主物品的第3、4维的位置。

3、初始化一个二维dp数组，第0个维度表示花的钱数，第1个维度表示可供选择的物品个数。当遇到当前钱数小于当前物品的价格或者当前物品是附件时，dp[i][j] = dp[i][j-1];其他情况时，依次进行判断并保留最大的满意度。

4、该算法还可以对空间和时间进行优化，有空做一下。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> vec(m+1,vector<int>(3));
    for(int i=1;i<m+1;i++){
        int t1,t2,t3;
        cin>>t1>>t2>>t3;
        vec[i][0] = t1/10;
        vec[i][1] = t2;
        vec[i][2] = t3;
        if(t3 != 0)
            vec[t3].push_back(i);
    }

    vector<vector<int>> dp(n/10 + 1,vector<int>(m+1,0));
    for(int i=1;i<n/10+1;i++){
        for(int j=1;j<m+1;j++){
            if(vec[j][2] != 0 || i<vec[j][0])
                dp[i][j] = dp[i][j-1];
            else{
                int temp = i-vec[j][0];
                dp[i][j] = max(dp[temp][j-1] + vec[j][0]*vec[j][1],
                               dp[i][j-1]);
                int len = vec[j].size();
                if(len == 4 && temp>=vec[vec[j][3]][0])
                    dp[i][j] = max(dp[i][j],
                                   dp[temp-vec[vec[j][3]][0]][j-1]
                                   + vec[j][0]*vec[j][1]
                                   +vec[vec[j][3]][0]*vec[vec[j][3]][1]);
                if(len == 5){
                    if(temp>=vec[vec[j][3]][0])
                        dp[i][j] = max(dp[i][j],
                                       dp[temp-vec[vec[j][3]][0]][j-1]
                                       + vec[j][0]*vec[j][1]
                                       +vec[vec[j][3]][0]*vec[vec[j][3]][1]);
                    if(temp>=vec[vec[j][4]][0])
                        dp[i][j] = max(dp[i][j],
                                       dp[temp-vec[vec[j][4]][0]][j-1]
                                       + vec[j][0]*vec[j][1]
                                       +vec[vec[j][4]][0]*vec[vec[j][4]][1]);
                    if(temp>=vec[vec[j][4]][0] + vec[vec[j][3]][0])
                        dp[i][j] = max(dp[i][j],
                                       dp[temp-vec[vec[j][4]][0]-vec[vec[j][3]][0]][j-1]
                                       + vec[j][0]*vec[j][1]
                                       +vec[vec[j][4]][0]*vec[vec[j][4]][1]
                                       +vec[vec[j][3]][0]*vec[vec[j][3]][1]);
                }
            }
        }
    }    
    cout<<dp[n/10][m] * 10<<endl;
    return 0;
}