多重背包问题(二)

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

多重背包问题 III

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出一个整数,表示最大价值。

数据范围:

image.png

输入样例:

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例:

10

思路分析

本题用到了单调队列(滑动窗口进行优化),对该知识点不了解或不熟悉的同学请先读博客:单调队列,附上一张y总讲课截图辅助理解:

4.png

image.png

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010, M = 20010;
int v[N], w[N], s[N];
int f[N][M];
int q[M];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; i ++ ) 
    {
        for (int r = 0; r < v[i]; r ++ )
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i] )
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++;
                while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j]) tt --;
                q[ ++ tt] = j;
                f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

和 多重背包问题 I 一样的优化方式,我们发现在计算f[i][j]的时候只使用了f[i−1][j],但是不可以使用 01背包的优化方法,因为我们使用的是 滑动窗口,这致使我们只能正向枚举体积。

滚动数组

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20010;
int f[2][N];
int q[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        int v, w, s;
        cin >> v >> w >> s;
        for (int r = 0; r < v; r ++ )
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v)
            {
                while (hh <= tt && j - q[hh] > s * v) hh ++;
                while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v * w <= f[(i - 1) & 1][j]) tt --;
                q[ ++ tt] = j;
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v * w;
            }
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}

拷贝数组

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
int f[N], g[N];
int q[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        memcpy(g, f, sizeof f);
        int v, w, s;
        cin >> v >> w >> s;
        for (int r = 0; r < v; r ++ )
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v)
            {
                while (hh <= tt && j - q[hh] > v * s) hh ++;
                while (hh <= tt && g[q[tt]] + (j - q[tt]) / v * w <= g[j]) tt --;
                q[ ++ tt] = j;
                f[j] = g[q[hh]] + (j - q[hh]) / v * w;
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

庆功会

题目要求

题目描述:

为了庆贺班级在校运动会上取得全校第一名成绩,班主任决定开一场庆功会,为此拨款购买奖品犒劳运动员。

期望拨款金额能购买最大价值的奖品,可以补充他们的精力和体力。

输入格式:

第一行二个数 n ,m ,其中 n 代表希望购买的奖品的种数,m  表示拨款金额。


接下来 n  行,每行 3 个数,v 、w 、s ,分别表示第I种奖品的价格、价值(价格与价值是不同的概念)和能购买的最大数量(买0件到s件均可)。

输出格式:

一行:一个数,表示此次购买能获得的最大的价值(注意!不是价格)。

数据范围:

n≤500,m≤6000,

v≤100,w≤1000,s≤10

输入样例:

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

输出样例:

1040

思路分析

裸题,不做解释,本题用最暴力的解法即可 A C ,有兴趣的读者可以对代码进行二进制优化和单调队列的优化,优化后的代码会放到评论区。

代码

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




目录
相关文章
|
数据采集 Web App开发 数据挖掘
利用Python和Selenium实现定时任务爬虫
利用Python和Selenium实现定时任务爬虫
|
1月前
|
弹性计算 人工智能 安全
阿里云99元云服务器购买与使用指南:2核2G3M带宽,续费同价,个人和企业新老用户同享
阿里云99元云服务器以经济型e实例(ecs.e-c1m2.large)为载体,配置2核2G、40GB ESSD Entry云盘、3Mbps固定带宽与1个IPv4公网IP,属标准ECS实例,支持VPC、安全组、快照及备案。活动有效期至2029年3月31日,采用"续费同价",活动期内每年可按99元续费一次,续费时不得变更配置。个人实名主体限保1台,企业主体限保1台99元e实例或1台199元u1实例,二者不可同时持有,可搭配域名、SSL、备案及RDS等组合套餐,适合建站、开发测试、小程序后端等轻中度场景。
|
8月前
|
人工智能 运维 搜索推荐
AI语音客服落地之困:企业要的是“降本工具”,但用户要的是“解决问题”
AI语音客服落地难,主因非技术不足,而是企业误将其当作“降本工具”而非“体验升级系统”。认知偏差、运营缺失、成本误判、技术适配四大困境交织。破局关键在于转向“人机协同增强思维”,以客户体验为本,构建持续迭代的运营机制。
|
10月前
|
存储 人工智能 Java
综合门诊、中医门诊SaaS诊所管理信息系统源码,java云诊所系统
基于云服务的SaaS诊所管理系统,集成预约挂号、门诊诊疗、电子病历、药品管理、医保对接、AI辅助诊断等功能,支持多终端协同与LIS/PACS/监管平台无缝对接。采用Java+Vue2.0+SpringBoot+MySQL架构,数据加密传输存储,安全可靠。适用于各类门诊及连锁、社区医疗机构,实现全流程数字化管理。
791 3
|
11月前
|
安全 算法 BI
物业定位管理系统从核心技术优势、功能应用到落地价值详解
物业定位管理系统融合UWB与蓝牙技术,实现厘米级高精度定位,采用TDOA算法抗干扰、低延迟,支持电子围栏、轨迹回放、智能调度等功能,兼顾隐私保护与系统兼容性,助力物业降本增效30%,提升安全管控与运营智能化水平。
|
9月前
|
Rust 安全 JavaScript
告别 `print()`!用 VS Code 调试器高效定位 Bug
本文手把手教你用VS Code调试器替代低效`print`:5步定位“越打折越贵”Bug,零代码侵入、实时查变量、支持条件断点与表达式监视。免费、高效、安全——调试本该如此简单!
852 33
|
10月前
|
机器学习/深度学习 存储 缓存
零基础玩转RAG:手把手教你搞定文档切分与大模型微调
本文深入解析RAG中至关重要的文档切分技术,系统对比句子切分、固定长度、重叠窗口、递归切分和语义切分五种策略,结合代码示例与实战技巧(PDF/Markdown/代码处理),并提供量化评估与调优方法,助你夯实RAG基石。(239字)
1065 1
零基础玩转RAG:手把手教你搞定文档切分与大模型微调
|
12月前
|
移动开发 小程序 前端开发
用技术撬动本地流量:基于UniApp+ThinkPHP构建同城圈子小程序的全栈源码
在本地生活服务竞争激烈背景下,“同城圈子”成为连接用户与商家的核心。UniApp+ThinkPHP技术组合实现一次开发、多端覆盖,降低80%成本,提升上线效率与系统稳定性,助力创业者低成本抢占本地市场,高效迭代变现。
|
运维 监控 Java
Linux常用命令行大全:14个核心指令详解+实战案例
在服务器管理与开发运维领域,Linux 指令是构建技术能力体系的基石。无论是日常的系统监控、文件操作,还是复杂的服务部署与故障排查,熟练掌握指令的使用逻辑都是提升工作效率的核心前提。然而,对于初学者而言,Linux 指令体系往往呈现出“参数繁多易混淆”“组合使用门槛高”“实际场景适配难”等痛点——例如 ls 命令的 -l 与 -a 参数如何搭配查看隐藏文件详情,grep 与管道符结合时如何精准过滤日志内容,这些问题常常成为技术进阶的阻碍。
|
人工智能 Kubernetes API
应用网关的演进历程和分类
唯一不变的是变化,在现代复杂的商业环境中,企业的业务形态与规模往往处于不断变化和扩大之中。这种动态发展对企业的信息系统提出了更高的要求,特别是在软件架构方面。为了应对不断变化的市场需求和业务扩展,软件架构必须进行相应的演进和优化。网关作为互联网流量的入口,其形态也在跟随软件架构持续演进迭代中。我们下面就聊一聊网关的演进历程以及在时下火热的 AI 浪潮下,网关又会迸发怎样新的形态。
1295 179