求解决(不知道哪里有问题)

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

Neil_Seniorious @ 2022-05-26 13:05:38

#include<cstdio>
#include<windows.h>
int v,n;
int a[61],c[61],q[61];
bool p[61]={true};
int dp[32001];
int main() {
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++) {
        scanf("%d%d%d",a+i,c+i,q+i);
        c[i]=c[i]*a[i];
    }
    for(int i=1;i<=n;i++) {
        for(int j=v;j>=0;j--) {
            if(j>=a[i]) {
                if(p[q[i]]) {
                    if(dp[j]<=dp[j-a[i]]+c[i]) {
                        dp[j]=dp[j-a[i]]+c[i];
                        p[i]=true;
                    }
                }
            }
        }
    }
    printf("%d",dp[v]);
    return 0;
}

by kk_is_ethereal @ 2022-05-26 13:08:32

有5种决策:

1.不选;

2.选主件;

3.选主件+附件1;

4.选主件+附件2;

5.选主件+附件2+附件1;


by Neil_Seniorious @ 2022-08-04 15:46:58

@kk_is_ethereal

请问怎么实现呢

是枚举到主件的时候同时判断附件情况呢

还是枚举附件的时候判断与主件的关系呢

如果是前者的话,要怎么实现主附件关联( struct 里面多开些空间存储吗)

如果是后者的话,又要怎么存储主件状态呢


by Neil_Seniorious @ 2022-08-04 15:47:26

#include<stdio.h>
struct furniture{
    int money,haven,important;
}a[61];
int v,n;
int dp[32001];
int main(){
    scanf("%lld",&v,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].money,&a[i].important,&a[i].haven);
        a[i].money=a[i].money*a[i].important;
    }
    for(int i=1;i<=n;i++){
        for(int j=v;j>=a[i].money;j--){

        }
    }
    return 0;
}

by kk_is_ethereal @ 2022-08-04 16:09:47

#include<bits/stdc++.h>
using namespace std;
int n,m,w[61][3],v[61][3],f[32001];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int v1,w1,p1;
        scanf("%d%d%d",&v1,&w1,&p1);
        if(p1==0){
            w[i][0]=w1;
            v[i][0]=v1;
        }else{
            if(w[p1][1]==0){
                w[p1][1]=w1;
                v[p1][1]=v1;
            }else{
                w[p1][2]=w1;
                v[p1][2]=v1;
            }
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=n;j>=v[i][0];j--){
            f[j]=max(f[j],f[j-v[i][0]]+(v[i][0]*w[i][0]));
            if(j>=v[i][0]+v[i][1])f[j]=max(f[j],f[j-v[i][0]-v[i][1]]+(v[i][0]*w[i][0]+v[i][1]*w[i][1]));
            if(j>=v[i][0]+v[i][2])f[j]=max(f[j],f[j-v[i][0]-v[i][2]]+(v[i][0]*w[i][0]+v[i][2]*w[i][2]));
            if(j>=v[i][0]+v[i][1]+v[i][2])f[j]=max(f[j],f[j-v[i][0]-v[i][1]-v[i][2]]+(v[i][0]*w[i][0]+v[i][1]*w[i][1]+v[i][2]*w[i][2]));
        }
    }
    printf("%d",f[n]);
}

by kk_is_ethereal @ 2022-08-04 16:10:17

用一堆if判断


by kk_is_ethereal @ 2022-08-04 16:11:05

@Neil_Seniorious


by Neil_Seniorious @ 2022-08-04 16:48:37

啊这


|