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,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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!