算法学习系列(五十五):背包模型(三)

2024-05-04 16:28

本文主要是介绍算法学习系列(五十五):背包模型(三),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 引言
  • 一、潜水员
  • 二、背包问题求具体方案
  • 三、机器分配
  • 四、开心的今明
  • 五、金明的预算方案

引言

今天介绍的是背包模型,还是以题目的形式来介绍的。主要讲了背包问题求方案,就是由最优方案递推回去即可。还有就是一些比较经典的背包问题,其实明显能感觉到其实背包问题拿暴搜来做也是可以的,因为有些问题就是在中间夹杂着暴力枚举所有方案的思想,再加上数据范围小的,就可以拿暴搜来做。还有图论问题,求方案就是求一个拓扑序的一个过程,只不过要根据一些值来确定其是否存在入度,然后找方案,然后感觉这些东西一下子活起来了,题做得多了就会有这种感觉,继续加油吧!


一、潜水员

标签:DP、二维费用的背包问题

思路:这道题算是 宠物小精灵之收服 的一个变形,问的是在满足条件的情况下,最小消耗的重量是多少。我们定义状态 f [ i ] [ v 1 ] [ v 2 ] f[i][v1][v2] f[i][v1][v2] 代表从前 i i i 个物品中选体积至少为 v 1 , v 2 v1,v2 v1,v2 的所有选法的集合,属性为这些选法中最小的重量。那么本质上就是一个 01 01 01 背包问题,状态转移方程为 f [ i ] [ v 1 ] [ v 2 ] = m i n ( f [ i − 1 ] [ v 1 ] [ v 2 ] , f [ i − 1 ] [ m a x ( 0 , n − v 1 ) ] [ m a x ( 0 , m − v 2 ) ] + w ] f[i][v1][v2] = min(f[i-1][v1][v2],f[i-1][max(0,n-v1)][max(0,m-v2)]+w] f[i][v1][v2]=min(f[i1][v1][v2],f[i1][max(0,nv1)][max(0,mv2)]+w] ,因为我们状态定义的是体积至少为 v 1 , v 2 v1,v2 v1,v2 ,所以这里面的负数所代表的状态是合法的,所以就可以当作合法的状态进行转移。最后的初始化,因为定义所以最开始的 f [ 0 ] [ v 1 ] [ v 2 ] f[0][v1][v2] f[0][v1][v2] 都被初始化为正无穷,首先是因为状态不合法,其次是因为该状态不被其它状态所依赖,也就是不被选中,又因为求的是最小值,所以初始化为正无穷。如图所示为总结的定义状态时应该怎样初始化,具体选择哪一个还是要看题目的定义,这道题当然选择第三个。
在这里插入图片描述

题目描述:

潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸:一个为氧气,一个为氮气。让潜水员下潜的深度需要各种数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少?例如:潜水员有5个气缸。每行三个数字为:氧,氮的(升)量和气缸的重量:3 36 12010 25 1295 50 2501 45 1304 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249(1,2或者4,5号气缸)。你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。输入格式
第一行有2个整数 m,n。它们表示氧,氮各自需要的量。第二行为整数 k 表示气缸的个数。此后的 k 行,每行包括ai,bi,ci,3个整数。这些各自是:第 i 个气缸里的氧和氮的容量及气缸重量。输出格式
仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。数据范围
1≤m≤21,1≤n≤79,1≤k≤1000,1≤ai≤21,1≤bi≤79,1≤ci≤800
输入样例:
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例:
249

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 22, M = 80;int n, V1, V2;
int f[N][M];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> V1 >> V2 >> n;memset(f, 0x3f, sizeof f);f[0][0] = 0;for(int i = 1; i <= n; ++i){int v1, v2, w; cin >> v1 >> v2 >> w;for(int j = V1; j >= 0; --j){for(int k = V2; k >= 0; --k){f[j][k] = min(f[j][k], f[max(0,j-v1)][max(0,k-v2)]+w);}}}cout << f[V1][V2] << endl;return 0;
}

二、背包问题求具体方案

标签:背包问题、DP、求方案

思路:这道题首先就是一个 01 01 01 背包问题,要我们求最优方案的具体方案。我们可以把这个问题的解当作一个图来求解,如果上一个的最优解加上当前的物品等于当前的最优解,那么这个物品就被选择了。又因为这个问题求得是字典序最小的方案,因为这个方案可能不唯一,所以我们得按照从小到大来判断,所以我们得从后向前选择物品,跟从前向后选是一样的,因为初始值都为 0 0 0 所以就不用改变什么了。所以从后往前选最终的结果是 f [ 1 ] [ m ] f[1][m] f[1][m] ,然后再从前向后判断后一个的最后解加上当前的物品,是否为当前的最优解,然后输出即可,这样做肯定就为字典序最小的了,详细细节见代码。

题目描述:

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出 字典序最小的方案。这里的字典序是指:所选物品的编号所构成的序列。物品的编号范围是 1…N。输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。输出格式
输出一行,包含若干个用空格隔开的整数,表示最优解中所选物品的编号序列,且该编号序列的字典序最小。物品编号范围是 1…N。数据范围
0<N,V≤1000,0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 6
输出样例:
1 4

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1010;int n, m;
int v[N], w[N];
int f[N][N];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];for(int i = n; i >= 1; --i){for(int j = 0; j <= m; ++j){f[i][j] = f[i+1][j];if(j >= v[i]) f[i][j] = max(f[i][j], f[i+1][j-v[i]]+w[i]);}}for(int i = 1, j = m; i <= n; ++i){if(j >= v[i] && f[i][j] == f[i+1][j-v[i]]+w[i]){cout << i << " ";j -= v[i];}}return 0;
}

三、机器分配

标签:DP、分组背包问题

思路:这道题本质上是一个分组背包问题,就是每一个公司只能选择一种方案,对应的就是其价值,体积就是设备数,我们首先可以根据模板求出来其最大价值。然后就是求方案了,跟上一题是一样的,这里提一下求方案数就不能压缩状态了,因为就是要靠当前最优解和上一个最优解之间的关系才能判断当前物品选或是不选。然后就其实是一样的,只不过这里是物品的变成了 m m m 个了而已,再增加一维循环判断即可,详情见代码。

题目描述:

总公司拥有 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

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 11, M = 16;int n, m;
int w[N][M];
int f[N][M];
int ways[N];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);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){f[i][j] = f[i-1][j];for(int k = 1; k <= j; ++k){if(j >= k) f[i][j] = max(f[i][j], f[i-1][j-k] + w[i][k]);}}}cout << f[n][m] << endl;for(int i = n, j = m; i >= 1; --i){for(int k = 0; k <= m; ++k){if(j >= k && 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;
}

四、开心的今明

标签:DP、01背包问题

思路:首先这道题本质上还是一个 01 01 01 背包问题,不一样的是该物品的价值和体积是一样的,并且价值的计算需要乘以一个重要度,其余的就是模板了。

题目描述:

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 N 元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的 N 元。于是,他把每件物品规定了一个重要度,分为 5 等:用整数 1∼5 表示,第 5 等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。 设第 j 件物品的价格为 v[j],重要度为 w[j],共选中了 k 件物品,编号依次为 j1,j2,…,jk,则所求的总和为: 
v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk] 请你帮助金明设计一个满足要求的购物单。输入格式
输入文件的第 1 行,为两个正整数 N 和 m,用一个空格隔开。(其中 N 表示总钱数,m 为希望购买物品的个数) 从第 2 行到第 m+1 行,第 j 行给出了编号为 j−1 的物品的基本数据,每行有 2 个非负整数 v 和 p。(其中 v 表示该物品的价格,
p 表示该物品的重要度)输出格式
输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(数据保证结果不超过 108)。数据范围
1≤N<30000,1≤m<25,0≤v≤10000,1≤p≤5
输入样例:
1000 5
800 2
400 5
300 5
400 3
200 2
输出样例:
3900

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 3e4+10;int n, m;
int f[N];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> m >> n;for(int i = 1; i <= n; ++i){int w, p; cin >> w >> p;for(int j = m; j >= w; --j){f[j] = max(f[j], f[j-w]+w*p);}}cout << f[m] << endl;return 0;
}

五、金明的预算方案

标签:DP、背包问题、分组背包

思路:本质上还是一个分组背包的问题,就是这道题比较麻烦吧,需要枚举所有情况:选不选主件,选了主件不选附件或者选哪个附件都是要枚举到的,然后就是用到二进制枚举所有的情况,然后进行判断即可,详情见代码。

题目描述:

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件
的例子:如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是10元的整数倍)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,…,jk,则所求的总和为:v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk](其中*为乘号)请你帮助金明设计一个满足要求的购物单。输入格式
输入文件的第1行,为两个正整数,用一个空格隔开:N m,其中N表示总钱数,m为希望购买物品的个数。从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有3个非负整数v p q,其中v表示该物品的价格,p表示该物
品的重要度(1~5),q表示该物品是主件还是附件。如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号。输出格式
输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<200000)。数据范围
N<32000,m<60,v<10000
输入样例:
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
输出样例:
2200

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 61, M = 32010;int n, m;
int f[M];
PII father[N];
vector<PII> son[N]; int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> m >> n;for(int i = 1; i <= n; ++i){int v, p, q; cin >> v >> p >> q;if(!q) father[i] = {v,v*p};else son[q].push_back({v,v*p});}for(int i = 1; i <= n; ++i){for(int j = m; j >= 0; --j){for(int k = 0; k < 1 << son[i].size(); ++k){int v = father[i].x, w = father[i].y;for(int z = 0; z < son[i].size(); ++z){if(k >> z & 1){v += son[i][z].x;w += son[i][z].y;}}if(j >= v) f[j] = max(f[j], f[j-v]+w);}}}cout << f[m] << endl;return 0;
}

这篇关于算法学习系列(五十五):背包模型(三)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/959623

相关文章

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

基于Flask框架添加多个AI模型的API并进行交互

《基于Flask框架添加多个AI模型的API并进行交互》:本文主要介绍如何基于Flask框架开发AI模型API管理系统,允许用户添加、删除不同AI模型的API密钥,感兴趣的可以了解下... 目录1. 概述2. 后端代码说明2.1 依赖库导入2.2 应用初始化2.3 API 存储字典2.4 路由函数2.5 应

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)

《C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)》本文主要介绍了C#集成DeepSeek模型实现AI私有化的方法,包括搭建基础环境,如安装Ollama和下载DeepS... 目录前言搭建基础环境1、安装 Ollama2、下载 DeepSeek R1 模型客户端 ChatBo

SpringBoot快速接入OpenAI大模型的方法(JDK8)

《SpringBoot快速接入OpenAI大模型的方法(JDK8)》本文介绍了如何使用AI4J快速接入OpenAI大模型,并展示了如何实现流式与非流式的输出,以及对函数调用的使用,AI4J支持JDK8... 目录使用AI4J快速接入OpenAI大模型介绍AI4J-github快速使用创建SpringBoot

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1