背包求助
查看原帖
背包求助
828664
Llx2022楼主2023/9/25 21:01
#include<iostream>
#include<cstring>
using namespace std;
//n<=50
//V<=1e5
//G<=10
//Gpj<=100
//Pvj<=1e6
const int N=58;
int n,V;
int a[N];
int id[N*10];//500
int type[N*10];
int cnt;
int g[N*10];//组内物品花费
int p[N*10];//组内物品收益
const int Vv=1e5+8;
int f[N*10][Vv][2];
int main(){
    cin>>n>>V;
    for(int i=1;i<=n;i++){
        ++cnt;
        cin>>a[cnt];
        int num;
        cin>>num;
        // id[cnt]=i;//编号cnt所属组别
        type[cnt]=0;//主机
        for(int j=1;j<=num;j++){
            // id[++cnt]=i;
            ++cnt;
            type[cnt]=1;
            cin>>g[cnt]>>p[cnt];
        }
    }
    // for(int i=1;i<=cnt;i++){
    //     cout<<g[i]<<" "<<p[i]<<endl;
    // }
    // type[cnt+1]=0;
    for(int i=0;i<cnt;i++){
        for(int j=0;j<=V;j++){
            if(type[i+1]==0){
                f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0]);
                if(j-a[i+1]>=0) f[i+1][j][1]=max(f[i+1][j][1],max(f[i][j-a[i+1]][0],f[i][j-a[i+1]][1]));
            }
            else{
                // cout<<g[i+1]<<" "<<p[i+1]<<endl;
                f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0]);
                if(j-g[i+1]>=0) f[i+1][j][1]=max(f[i+1][j][1],max(f[i][j-g[i+1]][1]+p[i+1],f[i][j][1]));
                else f[i+1][j][1]=max(f[i+1][j][1],f[i][j][1]);
            }
            // cout<<f[i+1][j][0]<<" "<<f[i+1][j][1]<<endl;
            
        }   
        // cout<<"________________"<<endl;
    }
    int ans=0;
    for(int i=0;i<=V;i++){
        for(int j=0;j<2;j++){
            ans=max(f[cnt][i][j],ans);
        }
    }
    cout<<ans<<endl;
    return 0;
}
2023/9/25 21:01
加载中...