侧边栏壁纸
博主头像
Hope博主等级

努力赚钱的工科研究生

  • 累计撰写 362 篇文章
  • 累计创建 129 个标签
  • 累计收到 5 条评论
标签搜索

分组背包问题

Hope
2022-03-22 / 0 评论 / 0 点赞 / 277 阅读 / 901 字
温馨提示:
本文最后更新于 2022-03-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

一共有n组,每组里面有s个,每次只能从一组中选一个。

image.png


#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;

int f[N][N],S[N];
int V[N][N],W[N][N];
int n,m;

int main(){
    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=1;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;
}

同样可以优化成一维

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;

int f[N],S[N];
int V[N][N],W[N][N];
int n,m;

int main(){
    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 k = 1; k <= S[i]; k++){
                if(j >= V[i][k])f[j] = max(f[j],f[j - V[i][k]] + W[i][k]);
            }
        }
    }
    
    cout<<f[m];
    return 0;
}

0

评论区