AcWing 9. 分组背包问题    原题链接    中等

作者： 作者的头像   cqh小蒟蒻 ,  2020-02-24 11:24:14 ,  所有人可见 ,  阅读 5503

17


2

题解

草图.png

C++ 代码

算法1

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

使用和01背包一样的优化方法

算法2

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N],v[N][N],w[N][N],s[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;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 k=0;k<s[i];k++)
                if(v[i][k]<=j) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
        }
    }
    cout<<f[m];
    return 0;
}

3 评论

用户头像 
#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int f[N];  //只从前i组物品中选，当前体积小于等于j的最大值
int V[N] , W[N] , s;   //v为体积，w为价值，s代表第i组物品的个数
int n , v;

int main(){
    cin >> n >> v;//读入
    for(int i = 1 ; i <= n ; i++){//枚举第几组
        cin >> s;//读入
        for(int k = 1 ; k <= s ; k++){//读入
            cin >> V[k] >> W[k];  
        }
        for(int j = v ; j >= 0 ; j--){//枚举体积，参考01背包
            //f[j] = f[j];  //不选
            for(int k = 1 ; k <= s ; k++){//选择第几个物品好
                if(j >= V[k])     f[j] = max( f[j] , f[j-V[k]] + W[k] );  
            }
        }
    }
    cout << f[v] <<endl;
}
用户头像
Lucky_1215   2022-09-20 13:48         踩      回复

f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]); 为啥不是f[i-1][j]呀

用户头像
Zzint   2022-10-21 16:30         踩      回复

f[i-1][j]是不选的集合下才更新f[i][j] 压缩成一维数组就可以省略掉了