白银新兵 @ 2016-09-18 23:28:42
/* 金明的预算方案:
第一次接触的“有依赖背包问题”
思想:
我们的目的便是把依赖背包换做我们原本学过的0/1背包
其中一种方法便是:
f[j]表示分配j元钱的包最多能获得的价格*期望值
让依赖条件成为一格背包中的一格分枝问题
这道题只有4种情况:
1)只买主件: f[j]=max(f[j],f[j-vi[i]]+ci[i])
2)买主件和它的一号附件:f[j]=max(f[j],f[ j- vi[i] - vi[next[i][1] ]+ci[i]+ci[next[i][1]]])
3) 买主件和它的二号附件:f[j]=max(f[j],f[ j- vi[i] - vi[next[i][2] ]+ci[i]+ci[next[i][2]]])
4) 买主件和所有附件:f[j]=max(f[j],f[ j - vi[i] - vi[next[j][1] - vi[next[i][2] ]+ci[i]+ci[next[i][1]]+ci[next[i][2]]]])
*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,q;
bool ser[3205]; //判断 主件还是附件 1是主件,0是附件
int f[33000];
int vi[3205]; //表示 价格
int pi[3205]; //表示 期望值
int ci[3205]; //表示 价格*期望值
int next[1205][2]; //next[i][a]表示 主件i的a号附件
int max(int a,int b){
return a>b ? a : b;
}
void dp(){
for(int i=1;i<=m;i++) //枚举物品
for(int j=n;j>=vi[i];j--) //枚举价格
{
if(ser[i]){ //是主件
f[j]=max(f[j],f[j-vi[i]]+ci[i]);
if(j>=vi[i]+vi[next[i][1]]) f[j]=max(f[j],f[ j- vi[i] - vi[next[i][1] ]+ci[i]+ci[next[i][1]] ]);
if(j>=vi[i]+vi[next[i][2]]) f[j]=max(f[j],f[ j- vi[i] - vi[next[i][2] ]+ci[i]+ci[next[i][2]] ]);
if(j>=vi[i]+vi[next[i][1]]+vi[next[i][2]]) f[j]=max(f[j],f[ j - vi[i] - vi[next[i][1]] - vi[next[i][2] ]+ci[i]+ci[next[i][1]]+ci[next[i][2]] ]);
}
}
}
int main(){
cin>>n>>m;
memset(next,0,sizeof(0)); //都没有附件
memset(ser,1,sizeof(1));
memset(f,0,sizeof(0)); //初始化
for(int i=1;i<=m;i++){
cin>>vi[i]>>pi[i]>>q;
ci[i]=vi[i]*pi[i];
if(q){ //是附件
ser[i]=0;
if(!next[q][1]){ //目前该主件没有附件1
next[q][1]=i;
}
else next[q][2]=i;
}
//主件不考虑
}
dp();
int ans=f[n];
cout<<ans;
return 0;
}