我是星星 @ 2017-08-30 15:06:13
#include<iostream>
using namespace std;
int v[100],f[100][32001],k,r[100],p[100],o[100],n,m;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>p[i]>>o[i]; //分别读入为物品i的价值,重要度,主件序号
}
k=n;
for(int i=1;i<=n;i++)
if(o[i])
if(r[o[i]]==0)
{
v[++k]=v[o[i]]+v[i];p[k]=p[o[i]]+p[i];r[o[i]]=i; //r[i]表示物件i的第一个附件的序号
v[i]=0;p[i]=0; //o[i]表示物件i的主件的序号
}
else
{
v[++k]=v[o[i]]+v[i]+v[r[o[i]]];p[k]=p[o[i]]+p[i]+p[r[o[i]]];
v[++k]=v[o[i]]+v[i];p[k]=p[o[i]]+p[i];
v[i]=0;p[i]=0;
}
for(int i=1;i<=k;i++)
for(int j=m;j>=1;j--)
if(v[i]<=j)
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*p[i]);
else f[i][j]=f[i-1][j];
cout<<f[k][m];
return 0;
}
求帮忙
by Out_Land @ 2017-08-30 16:31:39
你的状态转移方程是对的吗??@2556937429lq
by 我是星星 @ 2017-08-30 16:32:59
对,但是我没有分组
by 我是星星 @ 2017-08-30 16:33:30
我想问我这种思路还有救吗
by Out_Land @ 2017-08-30 16:33:55
@2556937429lq 分啥组??
by 我是星星 @ 2017-08-30 16:36:26
就是我用的捆绑思路,吧主件和附件捆绑在一起,有几个策略,但是每组的策略只能选一个,
我的会重复选择,所以错了
by Out_Land @ 2017-08-30 16:37:26
@2556937429lq 哦哦
by Out_Land @ 2017-08-30 16:38:35
其实此题可用枚举,枚举每一种情况。
by 我是星星 @ 2017-08-30 16:38:37
嗯嗯
by 我是星星 @ 2017-08-30 16:39:11
你详细说一下
by Out_Land @ 2017-08-30 16:41:01
1:主件和附件全取
2:取主件和附件一
3:取主件和附件二
4:都不取
5:只取主件
~。~