(dp+ group backpack) acwing 9 Group knapsack problem

9. Group knapsack problem

Topic link https://www.acwing.com/problem/content/description/9/
subject ：


Method 1 ： There is no memory optimization , A two-dimensional . The idea is to compare each item in each group , But make two comparisons . The first time is with f[ k-1 ][ j ], The second time is with f[k][j].

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
int f[110][110],k=1;
int main(){
    
    int n,v;
    cin>>n>>v;
    for(int i=0;i<n;i++){
    
        int s,x,y;
        scanf("%d",&s);
        for(int j=1;j<=s;j++){
    
            scanf("%d%d",&x,&y);
            for(int z=v;z>=0;z--){
    
                f[k][z]=max(f[k][z],f[k-1][z]);
                if(z>=x)
                    f[k][z]=max(f[k][z],f[k-1][z-x]+y);
            }
        }
        k++;
    }
    cout<<f[k-1][v];
    return 0;
}

Method 2 ： To optimize the f, Into one dimension . The idea is , Take each group in a v Inside for comparison , Take the optimal value

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
int f[110],v[110][110],w[110][110],s[110];
int main(){
    
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    
        cin>>s[i];
        for(int j=1;j<=s[i];j++){
    
            cin>>v[i][j]>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++){
    
        for(int j=m;j>=0;j--){
    
            for(int z=1;z<=s[i];z++){
    
                if(j>=v[i][z])
                    f[j]=max(f[j],f[j-v[i][z]]+w[i][z]);
            }
        }
    }
    cout<<f[m];
    return 0;
}