AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

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

作者: 作者的头像   就是个渣渣 ,  2019-10-20 08:12:51 ,  所有人可见 ,  阅读 1170


0


概览

有N组物品和一个容量为V的背包
每组物品有若干,同组内的物品只能选一个

分组背包问题是枚举每组选哪个或者不选, 完全背包问题是枚举某个物品选几个或者不选

题解

状态表示

  • 集合: 只从前i组物品中选,且总体积不大于j的所有做法
  • 属性: Max

状态计算

f[i,j]
集合划分,对第i个组怎么操作?

对于第i组,不选,选第1个物品,选第2个物品,…, 选第k个物品

f[i-1,j] , f[i-1, j-v[i,k]] + w[i,k] k

用的是上层状态则从大到小枚举,用的是本层状态则从小到大枚举

代码

// 当没有思路时,回到最初的步骤去思考应该如何做
// f[i,j] 只从前i组物品中选,且总体积不大于j的所有选法的最大值
// f[i,j] 最多选一个,那么可以不选,选a, 选b, 选c, 等等
// f[i,j] = max(f[i-1,j], f[i-1,j-v[k]]+w[k]) 上层从大到小枚举

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main() {
    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 (j >= v[i][k]) // 务必使其有意义
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;
    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息