分组背包问题与背包问题求具体方案(二)

简介: AcWing算法提高课内容,本文讲解 动态规划

机器分配

题目要求

题目描述:

总公司拥有 M 台相同的高效设备,准备分给下属的 N  个分公司。


各分公司若获得这些设备,可以为国家提供一定的盈利。盈利与分配的设备数量有关。


问:如何分配这 M  台设备才能使国家得到的盈利最大?


求出最大盈利值。


分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数 M 。

输入格式:

第一行有两个数,第一个数是分公司数 N,第二个数是设备台数 M ;

接下来是一个 N ∗ M  的矩阵,矩阵中的第 i 行第 j  列的整数表示第 i 个公司分配 j台机器时的盈利。

输出格式:

第一行输出最大盈利值;

接下 N  行,每行有 2  个数,即分公司编号和该分公司获得设备台数。

答案不唯一,输出任意合法方案即可。

数据范围:

1≤N≤10,

1≤M≤15

输入样例:

3 3
30 40 50
20 30 50
20 25 30

输出样例:

70
1 1
2 1
3 1

思路分析

可以看做分组背包问题:即每个公司分配的设备数是唯一的,并且要求具体的分配方案,即:背包问题求具体方案;这里其实有两种写法,代码一为按照本博客中的题目:背包问题求具体方案 进行倒枚举,但需注意,倒枚举的话输出的应为:f [ 1 ] [ m ],另一种方法就是记录分配过程,这种方法就不需要进行倒枚举。

代码一

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15, M = 20;
int w[N][M];
int f[N][M];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> w[i][j];
    for (int i = n; i >= 1; i -- )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= j; k ++ )
                f[i][j] = max(f[i][j], f[i + 1][j - k] + w[i][k]);
    cout << f[1][m] << endl;   // 注意是 f[1][m]
    int j = m;
    for (int i = 1; i <= n; i ++ )
        for (int k = 0; k <= j; k ++ )
            if (f[i][j] == f[i + 1][j - k] + w[i][k])
            {
                cout << i << ' ' << k << endl;
                j -= k;
                break;
            }
    return 0;
}

代码二

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15, M = 20;
int w[N][M];
int f[N][M];
int ways[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> w[i][j];
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
    cout << f[n][m] << endl;
    int j = m;
    for (int i = n; i >= 1; i -- )
        for (int k = 0; k <= j; k ++ )
            if (f[i][j] == f[i - 1][j - k] + w[i][k])
            {
                ways[i] = k;
                j -= k;
                break;
            }
    for (int i = 1; i <= n; i ++ )
        cout << i << ' ' << ways[i] << endl;
    return 0;
}

能量石

题目要求

题目描述:

岩石怪物杜达生活在魔法森林中,他在午餐时收集了 N  块能量石准备开吃。

由于他的嘴很小,所以一次只能吃一块能量石。

能量石很硬,吃完需要花不少时间。

吃完第 i 块能量石需要花费的时间为 S i 秒。

杜达靠吃能量石来获取能量。

不同的能量石包含的能量可能不同。

此外,能量石会随着时间流逝逐渐失去能量。

第 i 块能量石最初包含 E i 单位的能量,并且每秒将失去 L i 单位的能量。

当杜达开始吃一块能量石时,他就会立即获得该能量石所含的全部能量(无论实际吃完该石头需要多少时间)。

能量石中包含的能量最多降低至 0 。

请问杜达通过吃能量石可以获得的最大能量是多少?

输入格式:

image.png

输出格式:

每组数据输出一个结果,每个结果占一行。

结果表示为 Case #x: y,其中 x 是组别编号(从 1  开始),y  是可以获得的最大能量值。

数据范围:

image.png

输入样例:

3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0

输出样例:

Case #1: 105
Case #2: 8
Case #3: 500

样例解释:

在样例 #1 中,有N=4个宝石。杜达可以选择的一个吃石头顺序是:

image.png

他一共获得了 105  单位的能量,这是能获得的最大值,所以答案是 105 。

在样本案例 #2 中,有 N=3个宝石。

无论杜达选择吃哪块石头,剩下的两个石头的能量都会耗光。

所以他应该吃第三块石头,给他提供 8 单位的能量。

在样本案例 #3 中,有N=2 个宝石。杜达可以:

image.png

所以答案是 500。

思路分析

image.png

memset(f, -0x3f, sizeof f);
f[0] = 0;

这样就能保证我们的每一个状态都是由初始状态转移而来,接下来进入贪心分析:

image.png

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 10010;
struct Stone{
    int s, e, l;
    bool operator < (const Stone &w) const{
        return s * w.l < w.s * l;
    }
}stone[N];
int f[M];
int main()
{
    int T;
    scanf("%d", &T);
    for (int C = 1; C <= T; C ++ )
    {
        int n;
        scanf("%d", &n);
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        int m = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int s, e, l;
            scanf("%d%d%d", &s, &e, &l);
            stone[i] = {s, e, l};
            m += s;
        }
        sort(stone + 1, stone + 1 + n);
        for (int i = 1; i <= n; i ++ )
            for (int j = m; j; j -- )
            {
                int s = stone[i].s, e = stone[i].e, l = stone[i].l;
                if (j >= s) f[j] = max(f[j], f[j - s] + max(0, e - (j - s) * l));
            }
        int res = 0;
        for (int i = 1; i <= m; i ++ ) res = max(res, f[i]);
        printf("Case #%d: %d\n", C, res);
    }
    return 0;
}










目录
相关文章
|
存储 缓存
什么是TS流?
什么是TS流?
1027 0
|
9月前
|
人工智能 弹性计算 云计算
阿里云服务器优惠价格全解析:1年、1个月、1小时费用标准+选型指南+实操技巧
2026年阿里云持续深耕普惠云计算领域,针对个人用户、开发者、中小企业及大型企业等不同群体,推出了覆盖全场景、全配置的服务器优惠政策,核心呈现“入门款长效低价、中高配阶梯降价、多计费模式灵活适配”的特点,优惠力度最大直降90%,彻底打破了“云计算高成本”的认知壁垒。本文基于阿里云官方最新定价、优惠活动政策及全网实测资料,详细拆解2026年阿里云服务器1年、1个月、1小时的具体费用标准,区分轻量应用服务器、ECS云服务器、GPU实例三大核心产品,补充计费模式解读、不同场景选型建议、优惠领取实操、成本优化技巧及常用代码命令,全程无无关平台信息,透明无隐藏消费,帮助各类用户精准核算成本、锁定优惠
2433 16
|
8月前
|
IDE 编译器 开发工具
Dev C++ 6.5安装与配置教程 Windows版:解压+管理员运行+自定义路径+中文设置指南
Dev-C++是Windows下轻量级C/C++集成开发环境(IDE),含多页编辑、项目管理、调试功能,内置编译器与链接器。本指南详解6.5版下载、管理员安装、D盘自定义路径及中文界面配置,助你快速上手开发。(239字)
|
5月前
|
存储 缓存 运维
从云端到产线:汽车生产线密钥注入系统的架构设计
本文剖析汽车量产中关键却易被忽视的环节——密钥注入系统(KDPS)。它并非KMS附属,而是直连产线节拍的执行系统。面对60秒节拍、多供应商ECU、物理可接触等严苛约束,需在安全、速度与兼容性间精准平衡:推荐密钥预生成+安全缓存、三重防护注入通道、可插拔适配层架构。
480 0
|
5月前
|
运维 Cloud Native 安全
云原生系统规划
本文系统阐述云原生核心体系:涵盖十二要素、DevOps安全理念;详解技术架构——服务化、弹性、可观测等七大原则及微服务、Service Mesh、Serverless等主流模式;提出五步实施路径,并结合PaaS平台实践,展现其在降本增效、提升稳定性与自动化水平等方面的显著价值。
424 0
|
6月前
|
存储 安全 5G
化工厂人员精确定位系统从技术实现、核心价值详解
2026年7月1日,《“工业互联网+危化安全生产”建设规范 第3部分:人员定位》(AQ 3064.3-2025)将正式实施。本文聚焦化工厂人员精确定位系统,剖析“人在哪难知、环境复杂、人员难管”三大痛点,详解UWB+蓝牙融合定位、工业级防爆设计等技术方案,并阐述实时定位、电子围栏、SOS救援等核心价值,助力危化安全迈向事前防控、精准管控新阶段。(239字)
|
6月前
|
数据采集 Linux API
阿里云部署 Hermes Agent/OpenClaw 保姆级图文流程:免费API配置与新手常见问题解答
OpenClaw(Clawdbot)作为一款具备长期记忆与个性化能力的AI助手,凭借爬虫、数据分析、自动化操作等功能成为高效的工作辅助工具,但其本地部署过程中存在的环境配置、网络限制、模型对接等问题,让零基础新手望而却步。2026年针对这一问题,本文整理了阿里云、MacOS、Linux、Windows11多平台的OpenClaw本地部署完整步骤,同时包含阿里云百炼免费大模型API配置方法,并对部署和使用中的常见问题逐一解答,让新手也能零门槛实现OpenClaw的本地搭建与功能使用。
609 0
|
7月前
|
人工智能 缓存 运维
企业如何根据应用场景选择Claude、GPT与Gemini
本文针对企业大模型选型,提出“任务-能力精准匹配”核心理念,结合GPT-5.4、Claude 4.6/Opus 4.6、Gemini 3.1 Pro特性,分场景推荐模型,给出分层落地、四大评估维度及统一接入层架构建议,助力降本增效与工程韧性提升。
829 0
|
人工智能 算法 搜索推荐
电商API的“AI革命”:全球万亿市场如何被算法重新定义?
AI+电商API正引领智能商业变革,通过智能推荐、动态定价与自动化运营三大核心场景,大幅提升转化率、利润率与用户体验。2025年,75%电商API将具备个性化能力,90%业务实现智能决策,AI与API的深度融合将成为未来电商竞争的关键基石。
|
监控 Java 时序数据库
性能监控之Telegraf+InfluxDB+Grafana实现JMX实时监控
【6月更文挑战15天】性能监控之Telegraf+InfluxDB+Grafana实现JMX实时监控
672 6
性能监控之Telegraf+InfluxDB+Grafana实现JMX实时监控