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 )的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出格式:

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

数据范围:

1T1000,

1M100

输入样例:

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<V20000,

0<n30

输入样例:

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。

输出格式:

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

数据范围:

1N100,

1M10000,

1Ai1000,

答案保证在 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;
}




目录
相关文章
|
人工智能
AI 古籍修复的意义
AI 古籍修复的意义
372 0
|
搜索推荐 Python
将微信聊天做成滚动视频,聊天记录滚动播放
Python实现滚动聊天记录视频制作教程
1494 0
|
12月前
|
Java 关系型数据库 MySQL
自动化测试项目实战笔记(一):JDK、Tomcat、MySQL、Jpress环境安装和搭建
这篇文章是关于自动化测试项目实战笔记,涵盖了JDK、Tomcat、MySQL、Jpress环境的安装和搭建过程,以及测试用例和常见问题总结。
235 1
自动化测试项目实战笔记(一):JDK、Tomcat、MySQL、Jpress环境安装和搭建
|
11月前
|
存储 前端开发 搜索推荐
ClkLog基于ClickHouse 的百万日活实测报告
自 ClkLog 上线以来,我们不断吸纳用户需求,提升产品的支持能力。今年下半年,我们遇到了日活跃用户数达到百万级别的客户。为了给 ClkLog 用户提供可靠的技术建议和解决方案,同时也为了节省成本,在Clickhouse官方支持下,我们在阿里云上对 ClickHouse 社区版、企业版进行了详细测试和成本分析。
|
网络虚拟化 网络架构
思科三层交换机配置步骤
思科三层交换机配置步骤
1091 6
思科三层交换机配置步骤
|
缓存 Java 数据库连接
提高检索效率的利器--Mybatis 的一级缓存和二级缓存执行顺序
提高检索效率的利器--Mybatis 的一级缓存和二级缓存执行顺序
358 0
|
机器学习/深度学习 人工智能 自然语言处理
自然语言处理:实现智能问答系统的关键技术
自然语言处理在实现智能问答系统中起着重要作用。通过文本预处理、信息检索、语义理解和答案生成等关键技术,我们可以构建高效准确的智能问答系统,为用户提供便捷的信息获取方式。随着深度学习等技术的发展,智能问答系统的性能还将得到进一步提升,为人们提供更加智能化的服务。
1095 0
|
缓存 小程序 API
小程序:浅谈小程序更新机制,发版后多久能全覆盖
小程序:浅谈小程序更新机制,发版后多久能全覆盖
789 0
|
数据挖掘 数据格式
R语言- ComplexHeatmap 绘制复杂热图示例
ComplexHeatmap是R语言中用于绘制复杂热图的一个重要包。它提供了一种灵活、高效、易于定制的方法来绘制热图,并支持多种数据类型和数据格式,支持包括多种热图类型,包括基本热图、聚类热图、分组热图、矩阵热图等。用户可以根据自己的需求选择不同的热图类型,并进行灵活的定制。在生物信息学、医学、生态学等领域得到广泛应用。 本文将通过一个复杂热图的创建示例分享 ComplexHeatmap的语法规则。
1223 0
|
Java 开发者
SpringBoot 实现批量文件上传|学习笔记
快速学习 SpringBoot 实现批量文件上传
1502 0
SpringBoot 实现批量文件上传|学习笔记