测试链接
测试链接2
思路
其实有依赖的背包可以看成一个状况更复杂的01背包问题，01背包只需要考虑装和不装，有依赖的背包，如这个模板，就是考虑装主件，还是不装主件，装主件的话要装几个附件，因此，实际看代码可以发现就是多加了几个if条件分支，仅此而已
题解
#include <bits/stdc++.h>
using namespace std;
const int N=1e2+10;
typedef long long ll;
struct node
{int v,w,q;int f1=-1,f2=-1;
}a[N];
int n,m,ans;
int dp[35005];
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>a[i].v>>a[i].w>>a[i].q;if(a[i].q!=0){if(a[a[i].q].f1>0){a[a[i].q].f2 = i;}else a[a[i].q].f1 = i;}}for(int i=1;i<=m;i++){for(int j=n;j>=1;j--){if(a[i].q>0)continue;else{int t = dp[j];int f1 = a[i].f1;int f2 = a[i].f2;if(j>=a[i].v)t=max(t,dp[j-a[i].v]+a[i].v*a[i].w);if(f1>0&&j>=a[i].v+a[f1].v)t = max(t,dp[j-a[i].v-a[f1].v]+a[i].w*a[i].v+a[f1].v*a[f1].w);if(f2>0&&j>=a[i].v+a[f2].v)t = max(t,dp[j-a[i].v-a[f2].v]+a[i].v*a[i].w+a[f2].w*a[f2].v);if(f1>0&&f2>0&&j>=a[i].v+a[f1].v+a[f2].v)t = max(t,dp[j-a[i].v-a[f1].v-a[f2].v]+a[i].w*a[i].v+a[f1].v*a[f1].w+a[f2].v*a[f2].w);dp[j]=t;}}}cout<<dp[n]<<endl;return 0;
}
不用结构体版本
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4;
int n,m;
int dp[N],w[N],v[N],ff[N];
int fans[N][2];
int main()
{cin>>n>>m;memset(fans,-1,sizeof(fans));for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;w[i]=a;v[i]=b*a;ff[i]=c;if(c==0)continue;else if(fans[c][0]==-1)fans[c][0]=i;else fans[c][1]=i; }for(int i=1;i<=m;i++){if(ff[i]!=0)continue;for(int j=n;j>=0;j--){if(j>=w[i])dp[j]=max(dp[j-w[i]]+v[i],dp[j]);if(fans[i][0]!=-1&&j>=w[i]+w[fans[i][0]])dp[j]=max(dp[j-w[i]-w[fans[i][0]]]+v[i]+v[fans[i][0]],dp[j]);if(fans[i][1]!=-1&&j>=w[i]+w[fans[i][1]])dp[j]=max(dp[j-w[i]-w[fans[i][1]]]+v[i]+v[fans[i][1]],dp[j]);if(fans[i][0]!=-1&&fans[i][1]!=-1&&j>=w[i]+w[fans[i][0]]+w[fans[i][1]])dp[j]=max(dp[j-w[i]-w[fans[i][0]]-w[fans[i][1]]]+v[i]+v[fans[i][0]]+v[fans[i][1]],dp[j]);}}cout<<dp[n]<<endl;return 0;
}