(dp+分組背包) acwing 9. 分組背包問題

9. 分組背包問題

題目連結https://www.acwing.com/problem/content/description/9/

題目：

方法一：沒有優化記憶體的做法，二維。思路就是拿每一個小組每一個物品來比較，但要做兩次比較。第一次就是和f[ k-1 ][ j ]，第二次就是和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;
}

           

方法二：優化了f,變成一維。思路就是,拿每一組在某個v裡面進行比較，取最優值

#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;
}