一道算是 dp 的板子题了。
题意大概就是 01 背包 + 捆绑。
首先回顾一下 01 背包，一个比较基础的 dp 题，状态转移方程也很好想，是 \(dp[i][j]=\max(dp[i][j],dp[i-1][j-w[i]]+v[i])\)。
代码实现如下：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,dp[1010][1010],v[1010],w[1010];//w[i]重量，v[i]价值
#define QwQ return 0;
int main()
{
//dp[i][j]:以 j 为容量为放入前i个物品(按 i 从小到大的顺序)的最大价值
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>w[i]>>v[i];
for(int i=1;i<=m;i++)//物品数量
for(int j=n;j>=0;j--)//质量->0
{
if(j<w[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
cout<<dp[m][n];
QwQ;
}
然后这题实际上就是 01 背包的捆绑，发现最多只能绑 \(2\) 个物品依赖于另一个物品，因此容易发现这道题相总共会分 \(4\) 种情况：
-
买主件；
-
买主件，并买第一个附件；
-
买主件，并买第二个附件；
-
买主件，并买第一，二个附件。
然后这题再套上 01 背包板子就做完了。
参考代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,dp[40010],x,y,z,w[40010],v[40010],w2[40010][5],v2[40010][5];
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
int main()
{
IOS;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
if(z==0)
w[i]=x,v[i]=x*y;
else
w2[z][++w2[z][0]]=x,v2[z][w2[z][0]]=x*y;
}
for(int i=1;i<=m;i++)
for(int j=n;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
if(j>=w[i]+w2[i][1])
dp[j]=max(dp[j],dp[j-w[i]-w2[i][1]]+v[i]+v2[i][1]);
if(j>=w[i]+w2[i][2])
dp[j]=max(dp[j],dp[j-w[i]-w2[i][2]]+v[i]+v2[i][2]);
if(j>=w[i]+w2[i][1]+w2[i][2])
dp[j]=max(dp[j],dp[j-w[i]-w2[i][1]-w2[i][2]]+v[i]+v2[i][1]+v2[i][2]);
}
cout<<dp[n];
QwQ;
}