题解 | #购物单#

只把主件当成真正的物品，附件从属于主件，用一个哈希表存主件到附件的映射，当成背包问题来做，对于有附件的主件，有四种情况，取其中的最大值。代码如下：

#include <bits/stdc++.h>

using namespace std;

struct goods{

int id,price,imp,sat;

};

int main() {

map<int,vector<goods>> hashtable;

vector<goods> v;

int n,money;

cin>>money>>n;

getchar();

for(int i=0;i<n;++i){

goods g;

int flag;

g.id=i+1;

cin>>g.price>>g.imp>>flag;

g.sat=g.price*g.imp;

//如果是附件

if(flag){

hashtable[flag].push_back(g);

continue;

}

v.push_back(g);

}

int dp[n+1][money+1];

memset(dp,0,sizeof(dp));

for(int i=1;i<=v.size();++i){

for(int j=0;j<=money;j+=10){

//没有附件

if(hashtable.find(v[i-1].id)==hashtable.end()){

if(j>=v[i-1].price) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1].price]+v[i-1].sat);

else dp[i][j]=dp[i-1][j];

}

//有附件

else{

//只买主件

if(j>=v[i-1].price) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1].price]+v[i-1].sat);

else dp[i][j]=dp[i-1][j];

//买主件和附件1

if(j>=v[i-1].price+hashtable[v[i-1].id][0].price){

dp[i][j]=max(dp[i][j],dp[i-1][j-v[i-1].price-hashtable[v[i-1].id][0].price]+v[i-1].sat+hashtable[v[i-1].id][0].sat);

}

//买主件和附件2

if(hashtable[v[i-1].id].size()==2){

if(j>=v[i-1].price+hashtable[v[i-1].id][1].price){

dp[i][j]=max(dp[i][j],dp[i-1][j-v[i-1].price-hashtable[v[i-1].id][1].price]+v[i-1].sat+hashtable[v[i-1].id][1].sat);

}

}

//买主件和两个附件

if(hashtable[v[i-1].id].size()==2){

if(j>=v[i-1].price+hashtable[v[i-1].id][0].price+hashtable[v[i-1].id][1].price){

dp[i][j]=max(dp[i][j],dp[i-1][j-v[i-1].price-hashtable[v[i-1].id][0].price-hashtable[v[i-1].id][1].price]+v[i-1].sat+hashtable[v[i-1].id][0].sat+hashtable[v[i-1].id][1].sat);

}

}

}

}

}

cout<<dp[v.size()][money];

return 0;

}