简要题意：本题主要考查有依赖的背包。 题解：01背包中，有主件和附件，必须先买该附件所属的主件，每个主件可以有 0 0 0个 1 1 1个或 2 2 2个附件，使每件物品的价格与重要度的乘积的总和最大。 1.背包：主要分为四种情况： 只选主件： f [ j ] = m a x ( f [ j ] , f [ j − m a i n c [ i ] ] + m a i n w [ i ] ) ; f[j]=max(f[j],f[j-main_{c[i]}]+main_{w[i]}); f[j]=max(f[j],f[j−mainc[i]]+mainw[i]); 选附件1： f [ j ] = m a x ( f [ j ] , f [ j − m a i n c [ i ] − a n c [ i ] [ 1 ] ] + m a i n w [ i ] + a n w [ i ] [ 1 ] ) ; f[j]=max(f[j],f[j-main_{c[i]}-an_{c[i][1]}]+main_{w[i]}+an_{w[i][1]}); f[j]=max(f[j],f[j−mainc[i]−anc[i][1]]+mainw[i]+anw[i][1]); 选附件2： f [ j ] = m a x ( f [ j ] , f [ j − m a i n c [ i ] − a n c [ i ] [ 2 ] ] + m a i n w [ i ] + a n w [ i ] [ 2 ] ) ; f[j]=max(f[j],f[j-main_{c[i]}-an_{c[i][2]}]+main_{w[i]}+an_{w[i][2]}); f[j]=max(f[j],f[j−mainc[i]−anc[i][2]]+mainw[i]+anw[i][2]); 都要： f [ j ] = m a x ( f [ j ] , f [ j − m a i n c [ i ] − a n c [ i ] [ 1 ] − a n c [ i ] [ 2 ] ] + m a i n w [ i ] + a n w [ i ] [ 1 ] + a n w [ i ] [ 2 ] ) ; f[j]=max(f[j],f[j-main_{c[i]}-an_{c[i][1]}-an_{c[i][2]}]+main_{w[i]}+an_{w[i][1]}+an_{w[i][2]}); f[j]=max(f[j],f[j−mainc[i]−anc[i][1]−anc[i][2]]+mainw[i]+anw[i][1]+anw[i][2]); 代码如下：
#include<iostream> #include<algorithm> #include<cstring> using namespace std; int main_c[66666],main_w[666666],f[666666]; int an_c[66666][6],an_w[66666][6],an_num[66666]; int n,m; int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int c,w,z; cin>>c>>w>>z; if(z==0)main_c[i]=c,main_w[i]=c*w; else { an_num[z]++; an_c[z][an_num[z]]=c; an_w[z][an_num[z]]=c*w; } } for(int i=1;i<=m;i++) for(int j=n;j>=main_c[i];j--) { f[j]=max(f[j],f[j-main_c[i]]+main_w[i]); if(j>=main_c[i]+an_c[i][1]) f[j]=max(f[j],f[j-main_c[i]-an_c[i][1]]+main_w[i]+an_w[i][1]); if(j>=main_c[i]+an_c[i][2]) f[j]=max(f[j],f[j-main_c[i]-an_c[i][2]]+main_w[i]+an_w[i][2]); if(j>=main_c[i]+an_c[i][1]+an_c[i][2]) f[j]=max(f[j],f[j-main_c[i]-an_c[i][1]-an_c[i][2]]+main_w[i]+an_w[i][1]+an_w[i][2]); } cout<<f[n]<<endl; return 0; }