背包问题+部分和问题总结--思维跃进过程+代码

好久之前写了不少背包题，之后做了一段时间没怎么遇到，这两天突然遇到发现自己已经忘光了，还是总结一下方便以后看的好。文章目录一、01背包问题暴力搜索记忆化搜索简洁DP二、完全背包问题普通DPDP优化一、01背包问题暴力搜索虽然明知道暴力搜索一般解决不了问题，但是还是了解一下的好，熟悉这种搜索的策略对思维启发很大。#include<iostream>#include<a...

Ordinary_yfz

328人浏览 · 2020-03-22 11:17:10

Ordinary_yfz · 2020-03-22 11:17:10 发布

好久之前写了不少背包题，之后做了一段时间没怎么遇到，这两天突然遇到发现自己已经忘光了，还是总结一下方便以后看的好。

一、01背包问题

在这里插入图片描述

暴力搜索

虽然明知道暴力搜索一般解决不了问题，但是还是了解一下的好，熟悉这种搜索的策略对思维启发很大。

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 10000
int w[MAX], v[MAX];//物品质量，物品价值
int n, W;//物品总数，物品总质量
//从第i个物品开始，取重量小于j的最大价值
int rec(int i, int j) {
	int res;
	if (i == n) res = 0;
	else if (j < w[i]) {
		res = rec(i + 1, j);//这个物品取不了，跳过
	}
	else {
		res = max(rec(i + 1, j - w[i]) + v[i], rec(i + 1, j));//取与不取两种情况的最大值
	}
}
void solve() {
	cout << rec(0, W) << endl;
}

记忆化搜索

暴力搜索会造成很多重复的搜索，这是我们要使用记忆化搜索最重要的原因。只需要简单的加入dp数组，避免一些重复搜索，我们就可以将效率提升很多。

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1000
#define MAXW 10000
int w[MAXN], v[MAXN];//物品质量，物品价值
int n, W;//物品总数，物品总质量
int dp[MAXN][MAXW];
//从第i个物品开始，取重量小于j的最大价值
int rec(int i, int j) {
	if (dp[i][j] >= 0) return dp[i][j];//如果已经找过了这个值，就不用再找了
	int res;
	if (i == n) res = 0;
	else if (j < w[i]) {
		res = rec(i + 1, j);//这个物品取不了，跳过
	}
	else {
		res = max(rec(i + 1, j - w[i]) + v[i], rec(i + 1, j));//取与不取两种情况的最大值
	}
	dp[i][j] = res;//每次找到一个新值，都将其记录起来。
}
void solve() {
	memset(dp, -1, sizeof(dp));
	cout << rec(0, W) << endl;
}

简洁DP

其实上面剪枝过后的搜索过程，已经可以抽象化成一个递推公式了，
在这里插入图片描述
有了递推公式，我们的函数可以进一步的简化

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1000
#define MAXW 10000
int w[MAXN], v[MAXN];//物品质量，物品价值
int n, W;//物品总数，物品总质量
int dp[MAXN][MAXW];
//从第i个物品开始，取重量小于j的最大价值
int rec() {
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= W; j++) {
			if (j < w[i]) dp[i][j] = dp[i - 1][j];
			else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
	return dp[n][W];
}
void solve() {
	memset(dp, 0, sizeof(dp));
	cout << rec() << endl;
}

二、完全背包问题

在这里插入图片描述

普通DP

不同之处在于，这里的物品不再是一个，如果是有限个，我们当然可以按照01背包将所有物品展开进行计算，但是这里是无穷个。于是我们的搜索要加上个数这个条件。令 $d p [i] [j]$ 为在前 $i$ 个物品中挑选质量不超过 $j$ 的物品总价值的最大值。
$dp[i][j]=\max_{k\geq0 \&\&k*w[i]\leq j}(dp[i-1][j-k*w[i]]+k*v[i])$
写为程序便是：

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1000
#define MAXW 10000
int w[MAXN], v[MAXN];//物品质量，物品价值
int n, W;//物品总数，物品总质量
int dp[MAXN][MAXW];
//从第i个物品开始，取重量小于j的最大价值
int rec() {
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= W; j++) {
			for (int k = 0; k*w[i] < j; k++) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
			}
		}
	}
	return dp[n][W];
}
void solve() {
	memset(dp, 0, sizeof(dp));
	cout << rec() << endl;
}

DP优化

三重循环一看就很不靠谱，怎么优化呢？其实很多简单的dp算法都会存在这种问题，比如。记住下面这张图作为多余计算的示例，3的重量为2，价值为3，可以看到 $d p [3] [3 k]$ 每个元素的计算都要依赖到 $d p [2] [1]$ ，而 $d p [3] [7]$ 中选择三个的情况是这样的 $d p [3] [7] = d p [3] [1] + 3 * 3$ ，而 $d p [3] [5]$ 选2个的情况是这样的 $d p [3] [5] = d p [3] [1] + 3 * 2$ ，看一下规律其实如果取了那么有 $d p [3] [7] = d p [3] [5] + 3$ ，如果没取 $d p [3] [7] = d p [2] [7]$ ，二者取最大我们就得到了 $dp[3][7]=\max\{dp[2][7],dp[3][5]+3\}$
在这里插入图片描述
这样一来我们的计算过程变成了什么样呢？

确实是大大减少了冗余的运算：

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1000
#define MAXW 10000
int w[MAXN], v[MAXN];//物品质量，物品价值
int n, W;//物品总数，物品总质量
int dp[MAXN][MAXW];
//从第i个物品开始，取重量小于j的最大价值
int rec() {
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= W; j++) {
			if (j < w[i]) dp[i][j] = dp[i - 1][j];
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);//与01背包的差别
		}
	}
	return dp[n][W];
}
void solve() {
	memset(dp, 0, sizeof(dp));
	cout << rec() << endl;
}

仔细一看其实完全背包的问题与01背包问题的差别在于，dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);//与01背包的差别，在这里如果我们选了一个，是在本行进行计算的dp[i][j - w[i]]+v[i]，而01背包要归属到上一行dp[i-1][j - w[i]]+v[i]。

三、01背包与完全背包的内存优化写法

01背包

01背包每个 $d p [i] [j]$ 元素的更新依赖于上一行的 $d p [i - 1] [j]$ 和 $d p [i - 1] [j - w [i]]$ ，也就是上方元素和左上方元素，如果只有一行的话，我们应该从右到左进行修改，以保证左侧元素不会变化。

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1000
#define MAXW 10000
int w[MAXN], v[MAXN];//物品质量，物品价值
int n, W;//物品总数，物品总质量
int dp[MAXW];
//从第i个物品开始，取重量小于j的最大价值
int rec() {
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = W; j >= w[i]; j--) {
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}
	return dp[W];
}
void solve() {
	memset(dp, 0, sizeof(dp));
	cout << rec() << endl;
}

完全背包

注意完全背包的写法和01背包的写法区别现在就在于j的循环方向，完全背包从左到右逐渐更新（右侧的更新依赖于左侧 $dp[3][7]=\max(dp[2][7],dp[3][5]+3)$ ，而 $d p [2] [7]$ 在第7个位置，我们判断到第3行了， $d p [3] [7]$ 的值默认就是 $d p [2] [7]$ 。

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1000
#define MAXW 10000
int w[MAXN], v[MAXN];//物品质量，物品价值
int n, W;//物品总数，物品总质量
int dp[MAXW];
//从第i个物品开始，取重量小于j的最大价值
int rec() {
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = w[i]; j <= W; j++) {
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}
	return dp[W];
}
void solve() {
	memset(dp, 0, sizeof(dp));
	cout << rec() << endl;
}

四、超大容量背包

在这里插入图片描述
对于超大容量背包的问题，我们显然不能再使用两个for循环，此时背包问题的灵活性就显示了出来，我们可以比较随意的更改DP针对的对象，只要能找到一个合理的状态转移方程。可以设dp[i][j]:在前i个物品中，找到价值等于j的最小质量，如果不存在就是一个inf，这样最后所有不是inf的dp[i][j]都代表这个价值i我们可以拼凑出来（很flexible，可以用于解决很多的问题，比如如何判断一个序列的任意整数之和是否能凑成某个数？)，如果dp[i][j]能拼凑出来，那么肯定有dp[i-1][j]能拼凑出来，或者dp[i-1][j-v[i]]存在。那么我们就得到了dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]，最终的结果值就是令dp[i][j]<=W的最大的j值。
换成代码

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100
#define MAXV 100
#define inf 1e9
int w[MAXN], v[MAXN];//物品质量，物品价值
int n, W;//物品总数，物品总质量
int dp[MAXN][MAXN*MAXV];
//从第i个物品开始，取重量小于j的最大价值
int rec() {
	fill(dp[0], dp[0] + MAXN * MAXV + 1, inf);
	dp[0][0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= MAXN * MAXV; j++) {
			if (j < v[i]) dp[i][j] = dp[i - 1][j];//j值小于当前v[i]，就直接从上层拿就好了
			else dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]]);//j值大于当前v[i]，可以凑
		}
	}
	int res = 0;
	for (int i = 1; i <= MAXN * MAXV; i++)if (dp[n][i] <= W)res = i;
	return res;
}
void solve() {
	cout << rec() << endl;
}

五、多重部分和问题

在这里插入图片描述
多重部分和问题其实也就是背包问题的一种延伸，我么可以使用dp[i]表示i值是否可以被拼凑出来，那么我们可以得到下面的函数

1-初始DP

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100
#define MAXV 100
#define MAXK 100000
#define inf 1e9
int m[MAXN], a[MAXN];//数字的数目，数字的值
int n, K;//数字个数，需要拼凑的值
int dp[MAXK];

int rec() {
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;
	int maxj = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= K; j++) {
			if (dp[j]) {//如果j值能拼凑出来
				for (int k = 0; k < m[i] && k*a[i] < K; k++) {
					dp[j + k * a[i]] = 1;
				}
			}
		}
		maxj += a[i] * m[i];
		if (maxj > K)maxj = K;
	}
	return dp[K];
}
void solve() {
	cout << rec() << endl;
}

2-强力剪枝

上面三重循环的效率非常的低，一般都过不了，所以我们有必要进行很多次的剪枝。我们来分析一下下面的四次剪枝，将我们算法的效率大大提升，一般都可以按时AC。

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100
#define MAXV 100
#define MAXK 100000
#define inf 1e9
int m[MAXN], a[MAXN];//数字的数目，数字的值
int n, K;//数字个数，需要拼凑的值
int dp[MAXK];

int rec() {
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;
	int maxj = 0;//剪枝1:maxj统计当前以经拼凑出的最大值
	for (int i = 0; i < n && !dp[K]; i++) {//剪枝2:一旦K值拼凑，就可以退出
		for (int j = maxj; j >= 0 && !dp[K]; j--) {//剪枝2
			if (dp[j]) {
				for (int k = 0; k < m[i] && k*a[i] < K; k++) {
					if (j + k * a[i] == K) { dp[K] = 1; break; }//剪枝3，拼凑成功就退出
					else if (dp[j + k * a[i]]) break;//剪枝4：凑出了已有值，退出
					else dp[j + k * a[i]] = 1;
				}
			}
		}
		maxj += a[i] * m[i];
		if (maxj > K)maxj = K;
	}
	return dp[K];
}
void solve() {
	cout << rec() << endl;
}

前三个都很好理解，重点在于剪枝4，比如我们以经拼凑出了dp[8],a[i]=4，那我们势必会拼凑出dp[12],dp[16]...，然后我们的j值从大到小，判断到了dp[4]，我们再一次拼凑出dp[8],dp[12]...，这是没有必要的，无论是dp[4]还是dp[0]，都没有必要计算，这就是剪枝4的直观解释。

天启AI社区

GitCode 天启AI是一款由 GitCode 团队打造的智能助手，基于先进的LLM（大语言模型）与多智能体 Agent 技术构建，致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话，还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力，真正做到“一句话，让 Al帮你完成复杂任务”。

更多推荐

对近期接触到的直播相关知识进行梳理

M3U8 文件是 HLS (HTTP Live Streaming) 协议的核心组件，它本质上是一个播放列表文件，包含媒体流的结构信息。直播与视频聊天的对比：我觉得直播是通过流媒体技术把现场的图像和声音采集后分发出去，供观众在线围观，可以认为是开放的，一般没有人数限制；而视频聊天是点对点的线上交流，是基于UDP/TCP的实时传输协议实现的。流媒体是通过互联网实时传输音视频内容的技术，用户无需等待完