蒟蒻50分求助

_Eureka_ @ 2019-08-01 21:06:18

#include<bits/stdc++.h>
using namespace std;
const int MAXN=32001;
const int NUM=61;
int f[NUM][MAXN],v[NUM][NUM]={0},w[NUM][NUM]={0},a[NUM]={0};
int main(){
    int n,m,cost,imp,k,q,tempx=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>cost>>imp>>q;a[q]++;
        v[q][a[q]]=cost;w[q][a[q]]=imp*cost;
        tempx=a[0];
    } 
    for(int i=1;i<=tempx;i++)
     for(int j=1;j<=a[i];j++)
      if(n-v[0][i]>=0)
       for(int V=n-v[0][i];V>=0;V--)
        if(v[i][j]<=V)
         f[i][V]=max(f[i][V],f[i][V-v[i][j]]+w[i][j]);
    for(int k=1;k<=tempx;k++)
     for(int V=n;V>=0;V--)
      for(int i=0;i<=n-v[0][k];i++)
       if(i+v[0][k]<=V)
        f[0][V]=max(f[0][V],f[0][V-i-v[0][k]]+f[k][i]+w[0][k]);
    cout<<f[0][n];
}

by _Eureka_ @ 2019-08-01 21:09:13

如果需要解释的话我就再说说qwq

by zyx912 @ 2019-08-01 21:35:31

很简单啊

#include<bits/stdc++.h>
using namespace std;
int dp[33000],w[70],w1[70],w2[70],v[70],v1[70],v2[70];
int main(){
    memset(dp,0,sizeof(dp));
    memset(w,0,sizeof(w));
    memset(w1,0,sizeof(w1));
    memset(w2,0,sizeof(w2));
    memset(v,0,sizeof(v));
    memset(v1,0,sizeof(v1));
    memset(v2,0,sizeof(v2));
    int V,n;
    cin>>V>>n;
    for(int i=1;i<=n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(c==0){
            w[i]=a;
            v[i]=b;
        }
        else{
            if(w1[c]==0){
                w1[c]=a;
                v1[c]=b;
            }
            else{
                w2[c]=a;
                v2[c]=b;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=V;j>=w[i];j--){
            if(j-w[i]>=0){
                dp[j]=max(dp[j],dp[j-w[i]]+w[i]*v[i]);
            }
            if(j-w[i]-w1[i]>=0){
                dp[j]=max(dp[j],dp[j-w[i]-w1[i]]+w[i]*v[i]+w1[i]*v1[i]);
            }
            if(j-w[i]-w2[i]>=0){
                dp[j]=max(dp[j],dp[j-w[i]-w2[i]]+w[i]*v[i]+w2[i]*v2[i]);
            }
            if(j-w[i]-w1[i]-w2[i]>=0){
                dp[j]=max(dp[j],dp[j-w[i]-w1[i]-w2[i]]+w[i]*v[i]+w1[i]*v1[i]+w2[i]*v2[i]);
            }
        }
    }
    cout<<dp[V];
    return 0;
} 

好解法吧！！！

by _Eureka_ @ 2019-08-02 22:35:35

@zyx912 谢谢大佬，我看看

by _Eureka_ @ 2019-08-02 22:38:33

@zyx912 我是先01背包每一组主附件，然后分组背包每一组，跟大佬不是一种方法呢qwq。我寻思着试一下这种方法，大佬那种方法我倒是会写，就是如果用我这种思路应该怎么写呢

by Capacito @ 2019-08-09 18:14:43

@编程小萌新 我用你这种思路后面都超时

by _Eureka_ @ 2019-08-11 14:06:39

@Capatico 是的qwq，难过，我看的是书上的思路，结果不对。。。