[蓝桥杯 2021 省 AB] 砝码称重（C++，01背包可行性）

题目描述

你有一架天平和 $N$ 个砝码, 这 $N$ 个砝码重量依次是 $W_1,W_2,\cdots ,W_N$ 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数: $W_1,W_2,W_3,\cdots ,W_N$ 。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

3
1 4 6

样例输出 #1

10

提示

【样例说明】

能称出的 10 种重量是: $1、2、3、4、5、6、7、9、10、11$ 。

$$\begin{array}{rl}& 1=1\\ & 2=6-4(\text{ 天平一边放 }6,\text{ 另一边放 4) }\\ & 3=4-1\\ & 4=4\\ & 5=6-1\\ & 6=6\\ & 7=1+6\\ & 9=4+6-1\\ & 10=4+6\\ & 11=1+4+6\end{array}$$

【评测用例规模与约定】

对于 $50\%$ 的评测用例, $1\le N\le 15$ 。

对于所有评测用例, $1\le N\le 100,N$ 个砝码总重不超过 $10^5$。

蓝桥杯 2021 第一轮省赛 A 组 F 题（B 组 G 题）。

解题思路：

对于任意一个砝码，有三种情况：

1）不放

2）放左侧（与物品同侧）

3）放右侧（与物品异侧）

我们从n号砝码开始，遍历每一种情况，也就是暴力搜索DFS

void dfs(int i, int sum) {//前i号物品
	if (i == 0) {
		if (sum > 0) {
			if (!book[sum]) {
				ans++;
				book[sum] = true;
			}
		}
		return;
	}

	dfs(i - 1, sum);//不选
	dfs(i - 1, sum - w[i]);//选，左侧
	dfs(i - 1, sum + w[i]);//选，右侧
}

接下来进行时间优化，最容易想到的是记忆

记忆策略：i和sum相同，停止搜索直接return（剪枝）

因为sum < 0会发生数组越界，所以初始调用dfs(n, max_w)，加上一个偏移量即可

void dfs(int i, int sum) {//前i号物品
	if (book[i][sum]) return;
	book[i][sum] = true;

	if (i == 0) {
		if (sum > max_w) ans++;
		return;
	}

	dfs(i - 1, sum);//不选
	dfs(i - 1, sum - w[i]);//选，左侧
	dfs(i - 1, sum + w[i]);//选，右侧
}

对于本题的数据，加上记忆之后的代码已经够用了，但是我们仍可以进一步优化

方法仍然是背包问题中常见的动态规划

实际上动态规划和暴力搜索一样是遍历每一种情况，不同在于动态规划对每一种情形只遍历一次，不会重复（从这个意义上讲，与记忆化搜索一致）

原因是不同于暴力DFS自顶向下搜索最终结果，DP从底层的结果出发逐级递归推导

而要想从底层的结果推导出上层的结果，有两个前提条件：（1）最优子结构；（2）无后效性

大致意思就是对于一个复杂的结构，可以找到它的一个简单的子结构（就像树和子树的关系），然后找出子结构的最优解，并且之后的选择如何不会影响已推导出的最优解

从当前写出来的记忆化搜索不能直观的看出如何动态规划，所以我们修改一下，尝试理解下面的代码

void dfs(int i, int sum) {//前i号物品
	book[sum] = true;
	if (i == 0) return;

	dfs(i - 1, sum);//不选
	dfs(i - 1, sum - w[i]);//选，左侧
	dfs(i - 1, sum + w[i]);//选，右侧
}

假设我们现在搜索过了所有的砝码，那么最后输出答案的步骤如下

dfs(n, sum);//加上偏移量sum，防止数组越界
for (int i = sum + 1; i <= 2 * sum; i++) ans += book[i];
cout << ans;

并不难懂吧qwq

我们现在再增加一个重量为w的砝码，之前已经形成的结果不会受我们如何添加这个砝码的影响，这就是无后效性

我们用来存储结果的book数组，就是最优子结构

现在我们需要做的就是对每一个为元素做如下尝试

new_book[i - w] = book[i];//放左边
new_book[i + w] = book[i];//放右边
new_book[i] = book[i];//不放

这样我们就得到了再增加一个砝码后的方案数

但是这样有三条语句，我们把它们合并为一条

new_book[i] = book[i - w] || book[i] || book[i + w];

虽然写法不一样，但是效果是一样的

理解了之后，我们就可以将我们的代码改进为动态规划的模式了

//01背包可行性
#include <iostream>
using namespace std;
const int max_n = 100;
const int max_w = 1e5;

int w[max_n + 1] = { 0 };//砝码
bool book[max_n + 1][2 * max_w + 1] = { false };//滚动数组
int ans = 0;

int main() {
	int n, sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		sum += w[i];
	}
	book[0][sum] = true;//初始化，没有砝码的时候自然只有0一种情况
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= 2 * sum; j++) {
			book[i][j] = (book[i - 1][j]) || //不选
				(j - w[i] >= 0 && book[i - 1][j - w[i]]) || //防止数组左越界 && 选，左侧
				(j + w[i] <= 2 * sum && book[i - 1][j + w[i]]);//防止数组右越界 && 选，右侧
		}
	}

	for (int i = sum + 1; i <= 2 * sum; i++) ans += book[n][i];
	cout << ans;
	return 0;
}

接下来，就是背包问题中很常见的滚动数组了，利用i % 2的性质把数组压缩到二维

AC代码如下

//01背包可行性
#include <iostream>
using namespace std;
const int max_n = 100;
const int max_w = 1e5;

int w[max_n + 1] = { 0 };//砝码
bool book[2][2 * max_w + 1] = { false };//滚动数组
int ans = 0;

int main() {
	int n, sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		sum += w[i];
	}
	book[0][sum] = true;//初始化
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= 2 * sum; j++) {
			book[i % 2][j] = (book[(i - 1) % 2][j]) || //不选
				(j - w[i] >= 0 && book[(i - 1) % 2][j - w[i]]) || //选，左侧
				(j + w[i] <= 2 * sum && book[(i - 1) % 2][j + w[i]]);//选，右侧
		}
	}

	for (int i = sum + 1; i <= 2 * sum; i++) ans += book[n % 2][i];
	cout << ans;
	return 0;
}

这样就从递归时的$132$ms -> 动态规划时的$88$ms

2023-1-12 博客发布
2023-3-10 改进了动态规划的理解和说明部分