rnqoj-6-有依赖背包

这道题目的由于每个主件最多只有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,0,sizeof(vis));    memset(v,0,sizeof(v));    memset(vs,0,sizeof(vs));    memset(w,0,sizeof(w));    memset(ww,0,sizeof(ww));    memset(dp,0,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;}