01背包问题及二维费用背包问题(一)

简介: 01背包问题及二维费用背包问题

前言

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

本篇包括以下题目:

⭐️ AcWing 423. 采药

⭐️ AcWing 1024. 装箱问题

⭐️ AcWing 278. 数字组合

⭐️ AcWing 8. 二维费用的背包问题

⭐️ AcWing 1020. 潜水员

⭐️ AcWing 1022. 宠物小精灵之收服


写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来,博主会立即改正!望大家海涵


本文需要先自修基础:背包问题

注:本文中的所有代码全部为优化后的代码,且不提供优化解释,解释请见:背包问题,其中有详细的解释。


AcWing 423. 采药

题目要求

题目描述:

辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。

为此,他想拜附近最有威望的医师为师。

医师为了判断他的资质,给他出了一个难题。

医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

如果你是辰辰,你能完成这个任务吗?

输入格式:

输入文件的第一行有两个整数 T 和 M ,用一个空格隔开,T  代表总共能够用来采药的时间,M 代表山洞里的草药的数目。

接下来的 M  行每行包括两个在 1 到 100 之间(包括 1 和 100 )的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出格式:

输出文件包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。

数据范围:

1≤T≤1000,

1≤M≤100

输入样例:

70 3
71 100
69 1
1 2

输出样例:

3

思路分析

01背包的裸题,f [ i ]表示总时间不超过 i 的情况下可以采到的草药最大价值,可以说就是把01背包中的体积和质量变换为了时间和草药价值,直接把模板改改数据范围扔上来即可。

代码

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

AcWing 1024. 装箱问题

题目要求

题目描述:

有一个箱子容量为 V ,同时有 n 个物品,每个物品有一个体积(正整数)。

要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

输入格式:

第一行是一个整数 V ,表示箱子容量。

第二行是一个整数 n ,表示物品数。

接下来 n  行,每行一个正整数(不超过10000 ),分别表示这 n 个物品的各自体积。

输出格式:

一个整数,表示箱子剩余空间。

数据范围:

0<V≤20000,

0<n≤30

输入样例:

24
6
8
3
12
7
9
7

输出样例:

0

思路分析

也是一道01背包的裸题,与模板不同的是,这里的体积即为模板中的体积也为模板中的价值,且需要注意题目问的是剩余空间,故需要用总空间去减去用掉的空间,f[i]表示的是在总体积不超过 i ii 的情况下箱子内的最大体积。

代码

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

AcWing 278. 数字组合

题目要求

题目描述:

给定 N 个正整数A1,A2,…,AN,从中选出若干个数,使它们的和为 M ,求有多少种选择方案。

输入格式:

第一行包含两个整数 N 和 M 。

第二行包含 N 个整数,表示A1,A2,…,AN。

输出格式:

包含一个整数,表示可选方案数。

数据范围:

1≤N≤100,

1≤M≤10000,

1≤Ai≤1000,

答案保证在 i n t 范围内。

输入样例:

4 4
1 1 2 2

输出样例:

3

思路分析

注意到前两题都是求的最大价值,本题和前两题的唯一区别就是求的是方案数,求最大我们不需要对 f 数组进行初始化操作,因为 f数组内的元素默认是0,0就是最小的情况了,而求决策数和最小价值的时候,就需要对我们的 f 数组的部分元素做修改,我们本题规定 f [ i ] 表示选出的数的和正好为 i的情况下的决策数,所以我们的 f [ 0 ]应该初始化为 1 ,代表的是和为 0 的情况下,有一种方法:即全部都不选,因为求的是决策数,故状态转移方程就不再是:f[j] = max(f[j], f[j - v] + w);,而应该改为:f[j] += f[j - a];

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int f[N];
int main()
{
    int n, m;
    cin >> n >> m;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int a;
        cin >> a;
        for (int j = m; j >= a; j -- )
            f[j] += f[j - a];
    }
    cout << f[m] << endl;
    return 0;
}




目录
相关文章
|
机器学习/深度学习 存储 监控
EFK部署及应用
EFK部署及应用
856 1
|
数据采集 存储 测试技术
Python生成随机数插件Faker的用法
Python生成随机数插件Faker的用法
957 0
|
5月前
|
弹性计算 负载均衡 监控
阿里云SLB负载均衡搭建网站集群完全指南:从入门到高可用架构实战
本文提供了一份完整的阿里云SLB负载均衡搭建网站集群的实战指南。首先阐述负载均衡的核心价值与SLB产品家族(ALB、NLB、CLB)的选型策略。接着详细讲解配置前的账号权限、网络规划与后端服务器准备。然后逐步深入核心配置环节,涵盖实例创建、监听设置、服务器组绑定、健康检查参数调优、会话保持机制以及HTTPS证书配置与域名URL转发规则。文章提供丰富的阿里云CLI和Python SDK代码示例,并深入探讨多可用区部署、弹性伸缩集成、安全组策略等最佳实践。最后针对网站集群运维中的常见问题给出解决方案,帮助读者从零开始构建高可用、高性能的云上网站集群架构。
|
4月前
|
人工智能 供应链 安全
大模型 API 接入的「三座大山」:成本、供应链与合规的工程解法
本文揭示企业接入大模型API面临的三大困境:成本失控(中转平台暗箱扣费)、供应链脆弱(号池封禁致服务中断)、合规升级(跨境数据与身份管理新规)。提出通过API网关可观测计量、Provider抽象路由、RAM+SLS+DataWorks构建身份-传输-审计三层合规体系,实现稳健可控的AI基础设施。
506 0
|
Go 开发工具
百炼-千问模型通过openai接口构建assistant 等 go语言
由于阿里百炼平台通义千问大模型没有完善的go语言兼容openapi示例,并且官方答复assistant是不兼容openapi sdk的。 实际使用中发现是能够支持的,所以自己写了一个demo test示例,给大家做一个参考。
|
运维 安全 测试技术
Hydra-SSH 漏洞安全防范
Hydra 是由 THC 组织开发的强力网络安全测试工具,主要用于对 SSH、FTP、HTTP 等协议进行认证爆破,适用于授权渗透测试与弱口令检测。其高效性依赖于优化的字典策略,强调质量优先,结合目标信息定制密码列表,提高破解成功率。
988 1
|
传感器 机器人 物联网
【免费开源】基于STM32的蓝牙小车/智能小车项目详解(附源码)
通过本项目,你可以系统掌握STM32外设控制、蓝牙通信、电机驱动和传感器数据处理技术,实现一辆可远程控制并具备避障功能的智能小车。该项目具有高度可扩展性,后续可增加循迹、自动寻路、摄像头等高级功能。
3698 43
【免费开源】基于STM32的蓝牙小车/智能小车项目详解(附源码)
|
10月前
|
数据采集 安全 数据管理
2026年企业数据系统建设方案设计与实践指南
随着数据成为核心生产要素,新型企业数据系统已升级为全链路价值中枢。本文围绕技术、场景与合规三大维度,评估瓴羊Dataphin等主流方案,助力企业高效选型与落地,推动数字化转型。
|
SQL 监控 物联网
嵌入式工程师学习路线(软件类)
嵌入式工程师学习路线(软件类)
2529 1
|
SQL Java Spring
Seata AT模式与TCC模式对比,我们应该选择哪种分布式事务解决方案
Seata AT模式与TCC模式对比,我们应该选择哪种分布式事务解决方案
3383 0