这道题目的由于每个主件最多只有2个附件,所以每一个主件和其附件可以分解成:
主件
主件+附件1
主件+附件2
主件+附件1+附件2
这样每一个主件何其附件就组成了一个分组。
每个分组里只能取一个(WA了多次。。。。)
这样就变成了分组背包问题。
for 每一个分组
for v...0(背包容量)
for 所有属于分组里的数
dp[x]=max(dp[x],dp[x-c[i]]+w[i]);
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<vector> using namespace std; vector<int>vec[101]; int vis[101]; int vs[101]; int ww[101]; int dp[100001]; int v[501]; int w[501]; int tops; void init(int m) { for(int i=0;i<=m;i++)vec[i].clear(); memset(vis,sizeof(vis)); memset(v,sizeof(v)); memset(vs,sizeof(vs)); memset(w,sizeof(w)); memset(ww,sizeof(ww)); memset(dp,sizeof(dp)); } vector<int>vec2[1001]; int ls=0; void add(int x,int y) { v[tops]=x; w[tops++]=y; vec2[ls].push_back(tops-1); } int main() { int n,m,i,j,q; cin>>n>>m; init(m); for(i=1;i<=m;i++) { cin>>vs[i]>>ww[i]>>vis[i]; vec[vis[i]].push_back(i); } int len; tops=0; for(i=1;i<=m;i++) { if(vis[i]==0) { int x,y; add(vs[i],ww[i]*vs[i]); len=vec[i].size(); for(j=0;j<len;j++) { x=vec[i][j]; add(vs[i]+vs[x],ww[i]*vs[i]+ww[x]*vs[x]); } if(len==2) { x=vec[i][0]; y=vec[i][1]; add(vs[i]+vs[x]+vs[y],vs[i]*ww[i]+vs[x]*ww[x]+vs[y]*ww[y]); } ls++; } } int k; for(i=0;i<ls;i++) { for(j=n;j>=0;j--) { for(k=0;k<vec2[i].size();k++) { int x=vec2[i][k]; if(j-v[x]>=0)dp[j]=max(dp[j],dp[j-v[x]]+w[x]); } } } int ans=0; for(i=0;i<=n;i++)ans=max(ans,dp[i]); cout<<ans<<endl; return 0; }