c++10分求助,暴力背包

gfsc @ 2022-08-05 19:25:26

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[65],imp[65],p[65];//重量 重要程度  对应主件 
int cnt[65];//cnt[i]表示i主件有多少个附件 
int dp[65][33000];//dp[i][j]表示i个物品用j个空间的最大值 
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>imp[i]>>p[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=dp[i-1][j];
            if(j-a[i]>=0){
                if(p[i]==0){
                    if(dp[i][j]<dp[i-1][j-a[i]]+a[i]*imp[i]){
                        dp[i][j]=dp[i-1][j-a[i]]+a[i]*imp[i];
                    }
                }
                else{
                    if(cnt[i]<=1&&dp[i][j]<dp[i-1][j-a[i]]+a[i]*imp[i]){
                        cnt[i]++;
                        dp[i][j]=dp[i-1][j-a[i]]+a[i]*imp[i];
                    }
                }
            }
        }
    }
    cout<<dp[n][m];
}

by zhsm_ @ 2022-08-05 19:41:46

#include<cstdio>
 #include<cstring>
 using namespace std;
 int n,m,t[60],f[32000],vv[60][60],pp[60][60],ans,cnt[60];
 struct kkk {
     int v,p,q;
 }a[60],pat[60][60];
 int max(int k,int uu) {
     if(k >= uu) return k;
     return uu;
 } 
 int main()
 {
     scanf("%d%d",&n,&m);
     for(int i = 1;i <= m; i++) {
         scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
         if(a[i].q) {//如果这个物品是附件 
             t[a[i].q]++;
             pat[a[i].q][t[a[i].q]].v = a[i].v;
             pat[a[i].q][t[a[i].q]].p = a[i].p;
             pat[a[i].q][t[a[i].q]].q = a[i].q; //存到对应主件分组中 
         }
     }
     for(int i = 1;i <= m; i++) {//n个物品 
         if(t[i]) {//如果当前物品为主件 
             memset(f,-1,sizeof(f));
             f[0] = 0;
             for(int j = 1;j <= t[i]; j++)//t[i]个附件 
                 for(int k = n - a[i].v;k >= pat[i][j].v; k--)//空间 
                     if(f[k - pat[i][j].v] != -1)
                         f[k] = max(f[k],f[k-pat[i][j].v] + pat[i][j].v * pat[i][j].p); 
             for(int j = 0;j <= n-a[i].v; j++)
                 if(f[j] >= 0) {
                     cnt[i]++;
                     vv[i][cnt[i]] = j + a[i].v;
                     pp[i][cnt[i]] = f[j] + a[i].v * a[i].p;
                 }
         }
         if(!a[i].q) {//只买主件 
             cnt[i]++;
             vv[i][cnt[i]] = a[i].v;
             pp[i][cnt[i]] = a[i].v * a[i].p;
         }
     }
     memset(f,0,sizeof(f));
     for(int i = 1;i <= m; i++)
         for(int j = n;j >= 0; j--)
             for(int k = 1;k <= cnt[i]; k++)
                 if(j >= vv[i][k])
                     f[j] = max(f[j],f[j-vv[i][k]] + pp[i][k]),ans = max(ans,f[j]);
     printf("%d",ans);
     return 0;
 }

by gfsc @ 2022-08-05 20:15:52

谢谢，膜拜