分组背包不知道怎么噶了,球球debug

P1064 [NOIP2006 提高组] 金明的预算方案

啃丁狗 @ 2023-12-24 09:12:19

我来说说我的思路吧,我是把每个组都都分好,最多一组五个(主,主+附1,主+附2,主+附12,或者不选)我把组分好以后放到新的数组r里面用01背包做,但只有20分,不知道哪里错了,求捞捞

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7ffff
using namespace std;
int n,m,top,acnum[800];
struct node{
    int v,p,q,zz[3];
}obj[70];
struct neww{
    int vp,v;
}r[1000000];
int f[500000];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&obj[i].v,&obj[i].p,&obj[i].q);
        if(obj[i].q==0){
            r[++top].vp=obj[i].v*obj[i].p;
            r[top].v=obj[i].v;
        }
        else{
            int M=obj[i].q;
            obj[M].zz[++acnum[M]]=i;
            r[++top].vp=obj[i].v*obj[i].p+obj[M].v*obj[M].p;//zz是指针,从主件指向附件编号,方便后来编组
            r[top].v=obj[i].v+obj[M].v;//编主+单附件的组
        }
    }
    for(int i=1;i<=m;i++){
        if(obj[i].q==0&&acnum[i]==2){
            int to=obj[i].zz[1],too=obj[i].zz[2];
            r[++top].vp=obj[i].v*obj[i].p+obj[to].v*obj[to].p+obj[too].v*obj[too].p;//编主+附件12那一组
            r[top].v=obj[i].v+obj[to].v+obj[too].v;
        }
    }
    for(int i=1;i<=top;i++)
      for(int j=n;j>=r[i].v;j--)
        f[j]=max(f[j],f[j-r[i].v]+r[i].vp);//01背包
    printf("%d",f[n]);
    return 0;
}

by 啃丁狗 @ 2023-12-24 10:54:35

已解决,决策问题


|