题解 | #购物单#不限制附件个数时的解法

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
    int n,m;
    cin>>n>>m;//n表示总钱数 m表示可购买的物品的个数
    vector<int> v;vector<vector<int>> nums;
    map<int,vector<vector<int>>> M;
    for(int i=1;i<=m;i++)
    {
        int v,p,q;//价值 重要度 主附件
        cin>>v>>p>>q;
        M[q].push_back({i,v,p,q});
    }
    for(int i=0;i<M[0].size();i++)
    {
        nums.push_back(M[0][i]);
        for(int j=0;j<M[M[0][i][0]].size();j++)
            nums.push_back(M[M[0][i][0]][j]);
    }
    vector<vector<int>> dp(nums.size()+1,vector<int>(n+1,0));
    int ans=0;
    for(int i=0;i<nums.size();i++)
    {  
        for(int j=10;j<=n;j+=10)
        {
            if(nums[i][3]==0)
            {
                if(nums[i][1]<=j)
                {
                    dp[i][j]=nums[i][1]*nums[i][2];
                    for(int k=i-1;k>=0;k--)
                        dp[i][j]=max(dp[i][j],dp[k][j-nums[i][1]]+nums[i][1]*nums[i][2]);
                }
            }
            else//需要保证选择附件，就必须选择主件
            {
                if(j-nums[i][1]>=0)
                {
                    for(int k=i-1;;k--)//i前面的数
                    {
					  //这两个判断条件保证必须选择主件
                        if(dp[k][j-nums[i][1]]>0)
                            dp[i][j]=max(dp[i][j],dp[k][j-nums[i][1]]+nums[i][1]*nums[i][2]); 
                        if(nums[k][3]==0)
                            break;
                    }
                }   
            }
            ans=max(ans,dp[i][j]);
        }
    }
   cout<<ans;
}
// 64 位输出请用 printf("%lld")