首页 > 编程语言 >【算法笔记】三种背包问题——背包 DP

【算法笔记】三种背包问题——背包 DP

时间:2024-09-08 23:28:32浏览次数:12  
标签:背包 int d% 算法 01 物品 mathcal DP

前言

背包(Knapsack)问题是经典的动态规划问题,也很有实际价值。

01背包

洛谷 P2871 [USACO07DEC] Charm Bracelet S
AtCoder Educational DP Contest D - Knapsack 1
有\(n\)个物品和一个总容量为\(W\)的背包。第\(i\)件物品的重量是\(w_i\),价值是\(v_i\)。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

knapsack

这是最原始的01背包问题(即每个物品只能选\(0\)或\(1\)次)。下面我们来看如何求解。
令\(f_{i,j}\)表示只考虑前\(i\)个物品的情况下,容量为\(j\)的背包所能装的最大总价值。则最终答案为\(f_{n,W}\),状态转移方程为:

\[f_{i,j}=\begin{cases} 0 & (i=0/j=0) \\ \max(f_{i-1,j},f_{i-1,j-w_i}+v_i) & (i>0,j\ge w_i) \end{cases} \]

依次递增\(i\),逐步增加问题规模即可求解。时间、空间复杂度均为\(\mathcal O(nW)\)。
在本题中,\(\mathcal O(nW)\)的空间复杂度容易MLE,因此考虑使用数组重复利用或者滚动表的优化。

压缩掉\(f\)的第一维,变成:

\[f_j=\max(f_j,f_{j-w_i}+v_i) \]

此时空间复杂度为\(\mathcal O(W)\)。
一定要牢记这个公式,注意使用时需倒序枚举\(j\),防止串连转移。参考代码:

#include <cstdio>
#define setmax(x, y) if(x < y) x = y
using namespace std;

int f[12881];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	while(n--)
	{
		int w, v;
		scanf("%d%d", &w, &v);
		for(int i=m; i>=w; i--)
			setmax(f[i], f[i - w] + v);
	}
	printf("%d\n", f[m]);
	return 0;
}

01背包还有一种简单变形,即求最小剩余空间,此时用\((\)总空间\(-\)最大可装空间\()\)即可。

#include <cstdio>
#define setmax(x, y) if(x < y) x = y
using namespace std;

int f[20005];

int main()
{
	int n, v;
	scanf("%d%d", &v, &n);
	while(n--)
	{
		int w;
		scanf("%d", &w);
		for(int i=v; i>=w; i--)
			setmax(f[i], f[i - w] + w);
	}
	printf("%d\n", v - f[v]);
	return 0;
}

扩展:对付更大的\(W\)

AtCoder Educational DP Contest E - Knapsack 2
本题和普通的01背包完全相同,只是数据范围改为\(n\le 100,W\le 10^9,v_i\le 10^3\)。

注意数据范围,\(W\le 10^9\)意味着只要开这么大的数组都会MLE,因此我们考虑修改dp状态。前看原来的dp状态,本质上就是“确定重量,求最大价值”,现在我们反过来,即“确定价值,求最小重量”。令\(f_{i,j}\)表示只用前\(i\)个物品,达到总价值为\(j\)所需的最小空间。由于\(n\le 100,v_i\le 10^3\),所以\(\sum v_i\le 10^5\),极限情况下dp数组只需要开\(n\times\sum v_i\approx10^7\)即可,相对而言会好很多。下面考虑dp状态转移方程:

\[f_{i,j}=\begin{cases} +\infin & (i=0,j\ne0) \\ 0 & (i\ge 0,j=0) \\ \min(f_{i-1,j},f_{i-1,j-v_i}+w_i) & (i>0,j>0) \end{cases} \]

其中,\(i=0,j\ne 0\)这种情况不存在,所以初始值为\(+\infin\)。最终答案,即为最大的\(j\),使得\(f_{n,j}\le W\),更新状态时可同时记录这个答案。

这种算法的时间和空间都可以优化:

  • 时间:对于每个\(i\),循环迭代\(j\)时只需到\(v_1+v_2+\dots+v_i\)即可,因为当前的总价值不可能超过这个值;
  • 空间:用与前面完全相同的方法,压缩掉第一维空间,变成\(f_j=\min(f_j,f_{j-v_i}+w_i)\)(注意要倒序枚举\(j\)

运用了两种优化的代码如下:

#include <cstdio>
#include <cstring>
using namespace std;

long long f[100005], t, tot, ans;

int main()
{
	int n, sz;
	scanf("%d%d", &n, &sz);
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	while(n--)
	{
		int w, v;
		scanf("%d%d", &w, &v);
		tot += v;
		for(int i=tot; i>=v; i--)
			if((t = f[i - v] + w) < f[i] && t <= sz)
			{
				f[i] = t;
				if(i > ans) ans = i;
			}
	}
	printf("%lld\n", ans);
	return 0;
}

完全背包

洛谷 P1616 疯狂的采药
有\(n\)个物品和一个总容量为\(W\)的背包。第\(i\)件物品的重量是\(w_i\),价值是\(v_i\)。每个物品可以使用无限次。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

这种背包与01背包唯一的不同之处在于,每个物品使用次数不限,所以参考01背包的dp状态:
令\(f_{i,j}\)表示只考虑前\(i\)个物品的情况下,容量为\(j\)的背包所能装的最大总价值,则有:

\[\begin{aligned} f_{i,j}=\max_{k=0}^{+\infin}\{f_{i-1,j-k\times w_i}\}+v_i\times k\\ =\max_{k=0}^{\lfloor\frac j{w_i}\rfloor}\{f_{i-1,j-k\times w_i}\}+v_i\times k \end{aligned} \]

可以发现,实际上只需要用\(f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)\)即可,因为此时的\(f_{i,j-w_i}\)会被\(f_{i,j-2w_i}\)更新,\(f_{i,j-2w_i}\)又会被\(f_{i,j-3w_i}\)更新,以此类推,这样算与前面的公式等效。

对比一下01背包和完全背包的状态转移方程:

\[\begin{aligned} f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i) \\ f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i) \end{aligned} \]

实际上,区别就在于一个是\(f_{i-1,j-w_i}\),一个是\(f_{i,j-w_i}\)。所以仍可以使用数组压缩,只需要改变一下循环顺序,是不是很神奇?
long long别忘了~

#include <cstdio>
#define setmax(x, y) if(x < y) x = y
using namespace std;

long long f[10000005];

int main()
{
	int sz, n;
	scanf("%d%d", &sz, &n);
	while(n--)
	{
		int w, v;
		scanf("%d%d", &w, &v);
		for(int i=w; i<=sz; i++)
			setmax(f[i], f[i - w] + v);
	}
	printf("%lld\n", f[sz]);
	return 0;
}

多重背包

洛谷 P1776 宝物筛选
有\(n\)个物品和一个总容量为\(W\)的背包。第\(i\)件物品的重量是\(w_i\),价值是\(v_i\),最多能选择\(m_i\)次。我们要选择一些物品,使这些物品的重量总和不超过背包容量,且价值总和最大。\(n\le100,\sum m_i\le10^5,W\le 4\times10^4\)。

很容易想到,可以转换成每件物品都被拆分成\(m_i\)个只能选一次的物品,即\(N=\sum m_i\)的01背包。很明显,这样做的时间复杂度是\(\mathcal O(W\sum m_i)\),会TLE。因此,我们可以优化拆分的方法,将\(m\)转化为\(x+\sum\limits_{j=0}^i 2^j\)的形式,举几个栗子:

  • \(5=(1+2)+2\),其中\(i=1,x=2\);
  • \(16=(1+2+4+8)+1\),其中\(i=3,x=1\);
  • \(31=(1+2+4+8+16)\),其中\(i=4,x=0\)。

这种方法的正确性这里就不详细说明了,主要依赖于二进制的拼凑。容易发现,数字\(m\)按这种拆分的方法会被拆分为\(\lceil\log_2m\rceil\)个数字的和,因此总时间复杂度为\(\mathcal O(W\sum\limits_{i=1}^n\log m_i)\),可以通过此题。

还有一种单调队列/单调栈优化,同样针对多重背包问题,时间复杂度为\(\mathcal O(nW)\),有时不一定优于二进制优化,这里就不多说了。下面给出二进制优化的参考程序。

#include <cstdio>
#define maxw 40004
#define setmax(x, y) if(x < y) x = y
using namespace std;

int n, w, f[maxw];

inline void add(int a, int b) // a: value, b: weight
{
	for(int i=w; i>=b; i--)
		setmax(f[i], f[i - b] + a);
}

int main()
{
	scanf("%d%d", &n, &w);
	while(n--)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		for(int i=0; (1<<i)<=c; i++)
			add(a << i, b << i), c -= 1 << i;
		if(c) add(a * c, b * c);
	}
	printf("%d\n", f[w]);
	return 0;
}

混合背包

没错,就是前三种放在一起的背包。不用的物品有不同的种类。比如洛谷 P1833 樱花,就是混合背包。不过,也不要慌,直接用个分支判断,比如:

for (循环物品种类) {
  if (是 0 - 1 背包)
    套用 0 - 1 背包代码;
  else if (是完全背包)
    套用完全背包代码;
  else if (是多重背包)
    套用多重背包代码;
}

实际上也不一定要这样,可以全部统一成混合背包:

  • 对于01背包,可选数目\(k_i=1\)。
  • 对于完全背包,可选数目\(k_i=\lceil\frac W{w_i}\rceil\)。

这里就不给出详细代码,有兴趣的读者可以自己尝试一下。

总结

让我们来总结一下三种基本背包DP的异同:

项目 01背包 完全背包 多重背包
适用场景 每件物品只能选择一次 每件物品可以无限选择 每件物品可以选择的次数有限
状态转移方程[1] \(\max(f_j,f_{j-w_i}+v_i)\) \(\max(f_j,f_{j-w_i}+v_i)\) 基本同01背包
时间复杂度[2] \(\mathcal O(nW)\) \(\mathcal O(nW)\) \(\mathcal O(W\sum\log k_i)\)
空间复杂度[3] \(\mathcal O(W)\) \(\mathcal O(W)\) \(\mathcal O(W)\)
编码难度

创作不易,如果觉得好就请给个三连,谢谢支持!


  1. 压缩掉第一维的\(f_j\),01背包为倒序枚举\(j\),完全背包为正序 ↩︎

  2. 完全背包为优化后的复杂度,多重背包为二进制优化的复杂度。 ↩︎

  3. 指压缩第一维后的dp数组大小。 ↩︎

标签:背包,int,d%,算法,01,物品,mathcal,DP
From: https://www.cnblogs.com/stanleys/p/18403699/algonotes-knapsack-dp

相关文章

  • 【算法笔记】Kruskal/Prim算法——求解最小生成树问题
    前言生活中经常遇到类似这种的问题:公路修建有一些城市,城市之间要修建高速公路,每两个城市之间都可以修双向的路。其中每两个城市之间修路都需要花费对应的金额。请问如何修路,使得总花费的金额最少,且任意两个城市之间都可以直接或间接通过修建的路来通行?实际上,我们可以把这种......
  • 【算法笔记】树状数组/Binary Indexed Tree/Fenwick Tree
    前言树状数组,即树形存储的数组,又称BinaryIndexedTree或FenwickTree。抛开它树形的存储结构,这种神奇的数据结构的应用看起来与「树」没什么关系:有一个序列\(A=(A_1,A_2,\dots,A_N)\),在不超过\(\mathcalO(\logN)\)的时间复杂度内完成下列操作:\(\to~\)求\([L,R]\)区间内所......
  • Cooley-Tukey FFT算法的非递归实现
    一维情况#include<iostream>#include<complex>#include<cmath>constdoublePI=3.14159265358979323846;//交换位置voidswap(std::complex<double>&a,std::complex<double>&b){std::complex<double>temp=a......
  • 【算法笔记】位运算详解
    0.前言突然想到位运算是个好东西,就来水一波文章了……注意:我把能想到的有关位运算的所有内容都放进来了,所以篇幅较长,请谅解!若有写的不清楚或者不够详细的地方欢迎在评论区补充,谢谢支持!本文中参考代码均使用C++编写。废话不多说,下面步入正题。1.基本运算有一定基础的可以......
  • 【算法笔记】最近公共祖先(LCA)问题求解——倍增算法
    0.前言最近公共祖先简称LCA(LowestCommonAncestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。这种算法应用很广泛,可以很容易解决树上最短路等问题。为了方便,我们记某点集\(S=\{v_1,v_2,\ldots,v_n\}\)的最近公共祖先为\(\text{LCA}(v_1,v_2,\ld......
  • 【算法笔记】【专题】RMQ 问题:ST表/树状数组/线段树
    0.前言好久没更算法笔记专栏了,正好学了新算法来更新……这也是本专栏的第一个专题问题,涉及到三种数据结构,如果写得有问题请各位大佬多多指教,谢谢!1.关于RMQ问题RMQ的全称是RangeMinimum/MaximumQuery,即区间最大/最小值问题。本文中,我们的算法以求最大值为例(最小值基本......
  • wordpress新增文章新增评论自动通知到微信
    研究了下,如何让wordpress新增文章或者新增评论的时候通知到微信。复制下方代码,粘贴到主题的functions.php文件中即可在wordpress6.6.1版本测试通过理论上支持5.0以上的wp,有问题可以留言反馈/*在pushhub个人中心复制你的token,填入下方获取token:https://www.pushhub.c......
  • 【算法笔记】树形DP算法总结&详解
    0.定义树形DP,又称树状DP,即在树上进行的DP,是DP(动态规划)算法中较为复杂的一种。1.基础令\(f[u]=~\)与树上顶点\(u\)有关的某些数据,并按照拓扑序(从叶子节点向上到根节点的顺序)进行\(\text{DP}\),确保在更新一个顶点时其子节点的dp值已经被更新好,以更新当前节点的\(\text{DP}\)值......
  • 最小二乘回归算法原理及Python实践
    最小二乘回归算法原理主要基于最小化误差平方和的思想,以找到数据的最佳函数匹配。以下是对其原理的详细阐述:一、基本原理最小二乘法(LeastSquaresMethod,简称LS)是一种数学优化技术,它通过最小化误差的平方和来寻找数据的最佳函数匹配。在回归分析中,最小二乘法被广泛应用于......
  • 偏最小二乘回归算法原理及Python实践
    偏最小二乘回归(PartialLeastSquaresRegression,PLS回归)是一种统计学和机器学习中的多元数据分析方法,特别适用于处理因变量和自变量之间存在多重共线性问题的情况。其原理主要可以归纳为以下几点:一.原理概述PLS回归通过投影分别将预测变量(自变量X)和观测变量(因变量Y)投......