动态规划--背包问题

🕗 发布于 2024-11-26 00:54 动态规划算法

🎮 背包问题

欢迎来到 动态规划的冒险世界！在这趟旅途中，你将化身为一位勇敢的冒险者，面临一个经典而深邃的挑战：如何在有限的资源下获得最大的收益。每一关都充满了挑战，准备好了吗？Let’s Go!

前言

背包问题是动态规划最经典的问题之一，在这里，我们初步学会如何使用动态规划解决问题

绝大部分情况下，动态规划步骤如下：

1.状态表示： $\to$ 集合描述

2.状态计算：划分集合，把当前状态转化为子集状态（注意不重不漏） $\to$ 进而写出状态转移方程

接下来，让我们到题目中理解这两步的含义吧！

讲解

1.01背包

$N$ 种物品，体积 $V$ 背包
物品体积 $v_i$ ，价值 $w_i$ （最多只能用一次）

思路：

状态表示： $\to$ 前 $i$ 种物品花费 $j$ 体积得到的最大价值

状态计算：第 $i$ 种物品 $\quad 选 \to dp[i-1][j-v_i]+w[i] \quad 不选 \to dp[i-1][j]$

求最大价值：状态转移方程 $\to dp[i][j] = max(dp[i-1][j-v_i]+w[i],dp[i-1][j])$

理解：

从第1种物品一件一件往后选，每一步都求所有体积下的最优解

全局最优解一定会从前面的某个局部最优解转移过来

例题：

洛谷P1048 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入

第一行有 $2$ 个整数 $T$ （ $\le T \le 1000$ ）和 $M$ （ $\le M \le 100$ ），用一个空格隔开， $T$ 代表总共能够用来采药的时间， $M$ 代表山洞里的草药的数目。

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

输出

输出在规定的时间内可以采到的草药的最大总价值。

样例输入

样例输出

思路

翻译题目

总时间 $\to$ 背包体积

采每种药的时间 $\to$ 物品体积

状态表示： $\to$ 前 $i$ 种物品花费 $j$ 体积得到的最大价值

状态计算：第 $i$ 种物品 $\quad$ 选 $\to dp[i-1][j-v_i]+w[i] \quad$ 不选 $\to dp[i-1][j]$

求最大价值：状态转移方程 $\to dp[i][j] = max(dp[i-1][j-v_i]+w[i],dp[i-1][j])$

代码

// 01背包
// 状态表示 dp[i][j] 前i种j体积最大价值
// 状态计算 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
#include <iostream>

using namespace std;

const int N = 110, M = 1010;

int n, V;
int dp[N][M];
int v[N], w[N]; 
// 我这里按照自己习惯定义的变量,可能和题目符号有些出入

int main ()
{
    cin >> V >> n;
    
    for (int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];
    
    // 开始动态规划,从前往后一个一个挑
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j <= V; j ++ )
        {
            // 选到第i种,花费j体积
            // 第i件没得选, 放不下
            if (j < v[i]) dp[i][j] = dp[i - 1][j];
            
            // 第i件有选或不选的权利
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
}
    
    // 输出答案
    cout << dp[n][V] << endl;
    
    return 0;
}

优化

还没完！还能再优化！ 🤭

观察上面代码，我们发现在挑到第 $i$ 件物品时，我们只会用到第 $i - 1$ 层的数据，而不会用到更前面的数据

故可以把 $d p [i] [j]$ 直接压缩到 $d p [j]$ ,遍历到第i种物品时， $d p [j]$ 在第 $i - 1$ 层的基础上更新到第 $i$ 层

对于体积 $j < v [i]$ 的直接保留原本的 $d p [j]$

注意为了避免第i层更新dp[j]用的数据已经被更新过，这里体积需要从大到小枚举，读者可以自行体会

代码

// 01背包1维
#include <iostream>
using namespace std;
const int N = 110, M = 1010;
int n, V;
int dp[M];
int v[N], w[N]; 

int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
    
    cin >> V >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ ) 
        for (int j = V; j >= v[i]; j -- ) // 从大到小枚举,小于v[i]的更新不了
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    
    cout << dp[V] << endl;
    return 0;
}

2.完全背包

$N$ 种物品，体积 $V$ 背包
物品体积 $v_i$ ，价值 $w_i$ （无限用）

思路：

模仿01背包的思路，按照以下步骤

状态表示： $d p [i] [j]$ 前 $i$ 种花 $j$ 体积的最大价值

状态计算： 01背包的子状态是第i种选/没选;完全背包可以无限选，子状态是第 $i$ 种选了 $k$ 个

转移方程： $dp[i-1][j-v_i] + w_i,dp[i-1][j-2v_i]+2w_i,\cdots)$

每一层都这样枚举，总体复杂度 $O(NV^2)$ ,显然过于复杂了，需要进一步优化转移方程

类似上面的， $-v_i] = max(dp[i-1][j-v_i],dp[i-1][j-2v_i] +w_i,dp[i-1][j-3v_i]+2w_i,\cdots)$

对比可得

$dp[i-1][j-v_i] + w_i,dp[i-1][j-2v_i]+2w_i,\cdots)$

$\qquad \quad \ =max(dp[i-1][j],dp[i][j-v_i]+w_i)$

如此一来便化简了许多

优化：

再考虑优化到 $1$ 维：

第 $i$ 层需要用到第 $i$ 层和第 $i - 1$ 层的数据，这不恰好是体积从小到大枚举得到的效果？

体积从小到大枚举，第 $i$ 层枚举到 $j$ 时 $dp_{i-1}[j-v_i]$ 已经被更新为了 $dp_i[j-v_i]$ ,而 $dp_{i-1}[j]$ 仍保留，符合题意

所以和01背包一样，这里也能压缩掉一维，只需体积从小到大枚举即可

例题：

洛谷P1616 疯狂的采药

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$ . 每种草药可以无限制地疯狂采摘。

$2$ . 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入

输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$ 。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。

输出

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

样例输入

样例输出

代码

// 完全背包1维
#include <iostream>
using namespace std;
const int N = 10010, M = 1e7+10;
int n, V;
long long int dp[M];
long long  v[N], w[N]; 

int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
    
    cin >> V >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i ++ ) 
        for (int j = v[i]; j <= V; j ++ )
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    
    cout << dp[V] << endl;
    return 0;
}

3.多重背包

$N$ 种物品，体积V背包 $
物品体积 $v_i$ ，价值 $w_i$ （每种最多选 $s_i$ 个）

思路：

状态表示: $d p [i] [j]$ 前 $i$ 种花 $j$ 体积的最大价值

状态计算:子状态：第 $i$ 种选了 $k$ 个( $\le k \le s_i$ )

转移方程:

$dp[i-1][j-v_i] + w_i,dp[i-1][j-2v_i]+2w_i,\cdots,dp[i-1][j-s_i \times v_i]+s_i \times w_i)$

总体复杂度 $O (N V S)$ ,当 $s_i$ 非常大时,需要优化

关键是从 $0$ 到 $s_i$ 枚举第 $i$ 种选了 $k$ 个效率太低了

优化：

$\Rightarrow$ 优化思路：把第 $i$ 个物品用二进制拆成多种组合: $2^0$ 个 $\quad 2^1$ 个 $\quad \cdots \quad 2^t 个$ ( $2^t \le s_i)$

将每种物品的 $2^k$ 个单独看作一个物品

则任意 $a_0 2^0 + a_12^1 + \cdots + a_t2^t$ ( $a_i = 0$ 或 $1$ )

进而再转化为01背包问题,这样对于每种物品,最多只需要讨论 $logs_i$ 个选与不选 $\to$ 复杂度优化到 $O (N V l o g S)$

思考:为何这里不能用完全背包类似的优化思路?

例题：

洛谷P1776 宝物筛选

题目描述

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 $W$ 的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$ ，重量为 $w_i$ ，每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入格式

第一行为一个整数 $n$ 和 $W$ ，分别表示宝物种数和采集车的最大载重。

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$ 。

$(n\leq \sum m_i \leq 10^5$ ， $0\le W\leq 4\times 10^4$ ， $1\leq n\le 100)$

输出格式

输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

样例输入

样例输出

代码

// 多重背包问题
#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = 4e4 + 10;

int n, V;
int dp[N];
int v[N], w[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> V;
    
    int cnt = 1; // 存储拆分后的物品种数
    int v1, w1, s1; // 未拆分
    for (int i = 1; i <= n; i ++ )
    {
        cin >> w1 >> v1 >> s1;
        
        // s1拆成1+2+4+8+……
        int k = 1;
        while (s1 - k > 0)
        {
            v[cnt] = v1 * k;
            w[cnt ++] = w1 * k;
            s1 -= k;
            k *= 2;
        }
        
        // 拆剩下的
        if(s1) v[cnt] = v1 * s1, w[cnt ++] = w1 * s1;
}
    
    n = cnt - 1;
    
    // 01背包
    for (int i = 1; i <= n; i ++ )
        for (int j = V; j >= v[i]; j -- )
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    
    cout << dp[V] << endl;
    
    return 0;
}

4.分组背包

$N$ 组物品，体积 $V$ 背包
组内每件物品体积 $v_{ij}$ ,价值 $w_{ij}$ ,每组物品种最多选1个

思路：

状态表示: $d p [i] [j]$ 前 $i$ 组花费 $j$ 体积的最大值

状态计算:子状态 $\to$ 上一组选了哪一个

状态转移方程:

$dp[i-1][j-v_{(i-1)1}] + w_{(i-1)1},dp[i-1][j-v_{(i-1)2}] + w_{(i-1)2},\cdots,dp[i-1][j-v_{(i-1)k}]+w_{(i-1)k})$

优化至一维 $\to$ 体积降序枚举(略)

例题：

洛谷P1757 通天之分组背包

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入

两个数 $m, n$ ，表示一共有 $n$ 件物品，总重量为 $m$ 。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$ ，表示物品的重量，利用价值，所属组数。

$\leq m \leq 1000$ ， $\leq n \leq 1000$ ， $1\leq k\leq 100$ ， $a_i, b_i, c_i$ 在 int 范围内。

输出

一个数，最大的利用价值。

样例输入

样例输出

代码

// 1维分组背包
#include<iostream>

using namespace std;

const int N = 1e3 + 10;

int dp[N];
int n, V;
int v[N][N], w[N][N], cnt[N];// cnt[]存每个组的物品数

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
cin >> V >> n;

int gm = 0;//存储最大组数
    int v1, w1, j;
for (int i = 1; i <= n; i ++ )
{
cin >> v1 >> w1 >> j;
v[j][++ cnt[j]] = v1;
w[j][cnt[j]] = w1;
gm = max(gm, j);
}

    n = gm;
    
// 开始动态规划
for (int i = 1; i <= n; i ++ )
for (int j = V; j >= 0; j -- )
for (int k = 0; k <= cnt[i]; k ++ ) // 判断要选该组的哪件物品
if(v[i][k] <= j)
dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);

cout << dp[V] << endl;

return 0;
}

结语

以上便是背包问题最基础的4类模型，实际上的题目可能会结合上其他算法(状态压缩、贪心、树形DP $\cdots$ )

又或是进行变式(求方案数,多目标 $\cdots$ )

篇幅有限，笔者就不多赘述，相信凭借各位的聪明才智，一定可以轻松应付 $(ง •_•)ง

原文地址：https://blog.csdn.net/mathematicians/article/details/144016070

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：性能监控利器：Ubuntu 22.04 上的 Zabbix 安装与配置指南
下一篇：Jackson、Gson、FastJSON三款JSON利器比拼

React-useEffect的使用
react提供的一个常用hook，用于在函数组件中执行副作用操作，比如数据获取、订阅或手动更改DOM。
阅读更多2024-11-26
记录第一次安装laravel项目
记录第一次安装laravel项目
阅读更多2024-11-26
navicat密码解密python
navicat解密
阅读更多2024-11-26
ApiChain-从迭代到项目
在并行开发期间，频繁把代码部署到服务器供前端调用显得非常麻烦，前端需要的仅仅是一个能返回他们所需要的正确的数据格式的接口，他们基于这个接口的返回报文构造界面。mock服务器通过给前端提供一个局域网的仅
阅读更多2024-11-26
Leetcode148. 排序链表(HOT100)
Leetcode148. 排序链表(HOT100)
阅读更多2024-11-26
[JLOI2014] 松鼠的新家（重链剖分+线段树）
题目传送门好好的一道紫题为什么降绿了……
阅读更多2024-11-26
LeetCode 4.寻找两个中序数组的中位数
的标记位）来找到合适的划分点，并在每次循环中，根据当前的。合并后有序数组左半部分的最大值必然是这两个值中的较大者。合并后有序数组右半部分的最小值必然是这两个值中的较小者。mid1和mid2的右边(
阅读更多2024-11-26
企业OA管理系统：Spring Boot技术深度解析
目前，界面设计已经成为对软件质量进行评价的一条关键指标，一个好的用户界面可以使用户使用系统的信心和兴趣增加，从而使工作效率提高，JSP技术是将JAVA语言作为脚本语言的，JSP网页给整个服务器端的JA
阅读更多2024-11-26
Java基于Spring Boot框架的房屋租赁系统，附源码
Java基于Spring Boot框架的房屋租赁系统。本文从用户的功能要求出发，建立了房屋租赁系统，系统中的功能模块主要是实现人中心、房屋类型管理、房屋信息、预约看房管理、合同信息管理、房屋报修管理、
阅读更多2024-11-26
Spring Boot教程之八：Spring Boot执行器（Actuator)
对于相同的用例，Spring Boot 提供了一个执行器依赖项，可用于监控和管理您的 Spring Boot 应用程序，通过 /actuator 和 /actuator/health 端点您可以达到监
阅读更多2024-11-26

动态规划--背包问题

🎮 背包问题

前言

分类

1.01背包

2.完全背包

3.多重背包

4.分组背包

讲解

1.01背包

思路：

理解：

例题：

优化

2.完全背包

思路：

优化：

例题：

3.多重背包

思路：

优化：

例题：

4.分组背包

思路：

例题：

结语

相关文章