算法
(分组背包) $O(n*m)$
C++ 代码
$对于每个主件,最多有四种选法$
$1、主$
$2、主+附件1$
$3、主+附件2$
$4、主+附件1+附件2$
$将这几种情况拆分出来即可。可以不使用状态压缩 最多分成四份,从其中选一件也就是分组背包。$
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=41000,M=30;
int f[N];
int n,m;
int e[N],ne[N],h[N],idx;
bool st[N];
int v[N];
int w[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
int v1[5];
int w1[5];
v1[1]=v[u];
w1[1]=w[u];
int n=1;
for(int i=h[u];i!=-1;i=ne[i])
{
n++;
int j=e[i];
v1[n]=v[j];
w1[n]=w[j];
}
if(n==3)
{
n++;
v1[n]=v1[2]+v1[3];
w1[n]=w1[2]+w1[3];
}
for(int i=2;i<=n;i++)
{
v1[i]+=v1[1];
w1[i]+=w1[1];
}
//分组背包,每件物品最多选一次
for(int j=m;j>=0;j--)
{
for(int i=1;i<=n;i++)
if(j>=v1[i])
f[j]=max(f[j],f[j-v1[i]]+w1[i]);
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>m>>n;
for(int i=1;i<=n;i++)
{
int p;
cin>>v[i]>>w[i]>>p;
w[i]*=v[i];
if(p==0)
{
st[i]=true;
}
else
{
add(p,i);
}
}
for(int i=1;i<=n;i++)
if(st[i]) dfs(i);
cout<<f[m]<<endl;
return 0;
}