WA第三个点，死活不知道

华恋_韵 @ 2020-07-23 15:24:02

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[80];
int v[80];
int k[80];
vector<int> g[80];
struct node{
    int w,v;
}a[80][5];
int dp[320010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int p;
        scanf("%d%d%d",&w[i],&p,&k[i]);
        v[i]=w[i]*p;//价值 
        if(k[i])g[k[i]].push_back(i);//塞入附件 
    }
    for(int i=1;i<=70;i++)
    {
        if(k[i]!=0)continue;
        a[i][1].v=v[i];//单独主件 
        a[i][1].w=w[i];
        if(g[i].size()==1)//主件和一个附件 
        {
            a[i][2].v=v[i]+v[g[i][0]];
            a[i][2].w=w[i]+w[g[i][0]];
        }
        if(g[i].size()==2)//主件和另一个附件，主件和两个附件 
        {
            a[i][3].v=v[i]+v[g[i][1]];
            a[i][3].w=w[i]+w[g[i][1]];
            a[i][4].v=v[i]+v[g[i][1]]+v[g[i][0]];
            a[i][4].w=w[i]+w[g[i][1]]+w[g[i][0]];
        }
    }
    for(int i=1;i<=70;i++)//组数 
        for(int l=n;l>=0;l--)//容量 
            for(int j=1;j<=4;j++)//分好的分组背包 
                if(l>=a[i][j].w)
                    dp[l]=max(dp[l],dp[l-a[i][j].w]+a[i][j].v);//转移 
    cout<<dp[n];
    return 0;
}

by 华恋_韵 @ 2020-07-23 15:24:21

很典型的，拿出来枚举组合，然后分组背包啊

by 华恋_韵 @ 2020-07-23 15:24:31

但就是不知道错哪里了

by kouylan @ 2020-07-23 15:37:33

@华恋_韵 在组合的时候，如果一个主件有两个附件，那他就不会计算主件和第一个附件的情况了呀

by kouylan @ 2020-07-23 15:38:10

附上代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[80];
int v[80];
int k[80];
vector<int> g[80];
struct node{
    int w,v;
}a[80][5];
int dp[320010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int p;
        scanf("%d%d%d",&w[i],&p,&k[i]);
        v[i]=w[i]*p;//价值 
        if(k[i])g[k[i]].push_back(i);//塞入附件 
    }
    for(int i=1;i<=70;i++)
    {
        if(k[i]!=0)continue;
        a[i][1].v=v[i];//单独主件 
        a[i][1].w=w[i];
        if(g[i].size()==1)//主件和一个附件 
        {
            a[i][2].v=v[i]+v[g[i][0]];
            a[i][2].w=w[i]+w[g[i][0]];
        }
        if(g[i].size()==2)//主件和另一个附件，主件和两个附件 
        {
            a[i][2].v=v[i]+v[g[i][0]];
            a[i][2].w=w[i]+w[g[i][0]];  //这两行要加上
            a[i][3].v=v[i]+v[g[i][1]];
            a[i][3].w=w[i]+w[g[i][1]];
            a[i][4].v=v[i]+v[g[i][1]]+v[g[i][0]];
            a[i][4].w=w[i]+w[g[i][1]]+w[g[i][0]];
        }
    }
    for(int i=1;i<=70;i++)//组数 
        for(int l=n;l>=0;l--)//容量 
            for(int j=1;j<=4;j++)//分好的分组背包 
                if(l>=a[i][j].w)
                    dp[l]=max(dp[l],dp[l-a[i][j].w]+a[i][j].v);//转移 
    cout<<dp[n];
    return 0;
}

by 华恋_韵 @ 2020-07-23 15:39:20

@kouylan 啊对，谢了谢了，感激不尽