01背包问题,复杂度O(n*m)
对于附属物品,不单独计算,只有在计算主物品的时候才计算它,每次碰到主物品,它最多选两个附属物品,那么在原01背包的基础上加两层循环枚举所有可能的搭配方式即可。
时间复杂度分析:由于每个附属物品最多被遍历3遍,所以多出来的复杂度是常数级的,所以总时间复杂度还是O(n*m)
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N = 65 , M = 32010;
int dp[M],v[N],p[N],q[N];
int main()
{
int n,m;
cin>>m>>n;
vector<int> a[N];
for(int i=1;i<=n;i++)
{
cin>>v[i]>>p[i]>>q[i];
if(q[i]) a[q[i]].push_back(i);
}
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
{
if(q[i]) continue;
if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+v[i]*p[i]); //选0个附属物品
int k=a[i].size(),vv,ww;
for(int c1=0;c1<k;c1++) //选1个附属物品
{
int x=a[i][c1];
vv=v[i]+v[x];ww=v[i]*p[i]+v[x]*p[x];
if(j>=vv) dp[j]=max(dp[j],dp[j-vv]+ww);
for(int c2=c1+1;c2<k;c2++) //选2个附属物品
{
x=a[i][c2];
vv+=v[x];ww+=v[x]*p[x];
if(j>=vv) dp[j]=max(dp[j],dp[j-vv]+ww);
}
}
}
cout<<dp[m]<<endl;
return 0;
}