自动搬运

查看原文

来自洛谷，原作者为

	lottle1212 **

搬运于2025-08-24 22:42:40，当前版本为作者最后更新于2023-06-23 10:52:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题传送门

Part 0

首先浏览题面，当看到数据范围 $n \leq 1000, w_i \leq 20, v_i \leq 20000$ 时，就容易想到 $\text{01}$ 背包做法。但是，为了让砖块的价值总和最大，我们不能直接对其进行 $\text{01}$ 背包，必须先将砖块排序。否则，如果让一块很大的砖先做，较小的砖就无法在此基础上进行转移（原本价值可以直接累加），从而完美避开最优解。

按照什么样的顺序进行排序呢（这一部分本人看了 @王熙文 大佬的题解才明白，但对其中的一些小错误进行更正）？

首先，我们有两块砖 $i, j$，使得 $w_i + v_i \leq w_j + v_j$，我们假设 $i$ 一定排在 $j$ 前，即 $j$ 可以排在前的情况，$i$ 必定能排在前。

设 $W$ 表示排在 $i, j$ 前砖块的质量和。若 $j$ 能排在前，则必须满足：

此时，若将 $i$ 排在前，则必须满足：

由于 $w_j \geq 0$，所以 $v_i \geq W$ 满足。接着，我们将 $v_i \geq W + w_j$ 移项，得：

然后，将表示 $i, j$ 关系的不等式 $w_i + v_i \leq w_j + v_j$ 也移项，得：

二者结合，得 $v_j - w_i \geq W$，即 $v_j \geq W + w_i$。由此，便证明了最初的假设。

Part 1

代码写起来就很容易了。需要注意的是，为方便转移，$\text{01}$ 背包中 $dp_i$ 表示前几块砖重量和为 $i$ 的最大价值。

AC Code

#include <bits/stdc++.h>
using namespace std;
int n, m, ans, dp[20030];
struct node { int w, v; } a[1010]; //砖块
bool cmp(node pre, node nxt) { return pre.w + pre.v <= nxt.w + nxt.v; } //排序 
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++ i) cin >> a[i].w >> a[i].v;
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; ++ i)
		for (int j = a[i].w + a[i].v; j >= a[i].w; -- j)
			dp[j] = max(dp[j], dp[j - a[i].w] + a[i].v), //01背包 
			ans = max(ans, dp[j]); //求最大 
	cout << ans;
	return 0;
}

自认为马蜂比较清晰简短，希望大家看得懂，并祝大家 Codeing 愉快。