自动搬运

查看原文

来自洛谷，原作者为

	lby_commandBlock 降橙了好难受 | 临时主页 https://www.luogu.com.cn/paste/pr8127fq

搬运于2025-08-24 23:06:50，当前版本为作者最后更新于2024-12-08 12:54:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

看到这些题目，就要想到这道题要用什么算法来做，例如这道题要动态规划。

下文中的 $p_i,c_i$ 均与题目描述一致。

思路

按照动态规划的步骤进行思考。动态规划五部曲。

1. dp 数组以及下标的含义。

设 $dp_{i,j}$ 为前 $i$ 个武器中购买，总花费不超过 $j$，以最优策略购买武器后，武器的强度和。

2. 递推公式。

• 若 $c_i > j$，即该武器的花费大于了总花费（下文称预算），则 $dp_{i,j}$ 就直接从 $dp_{i-1,j}$ 进行转移。

• 若 $c_i \leq j$，即该武器的花费小于预算，就有买和不买两种情况。

$$dp_{i,j}=\max\{{dp_{i-1,j-c_i}+p_i}_{买的情况},{dp_{i-1,j}}_{不买的情况}\} $$

3. dp 数组如何初始化。

由于 dp 要求最大的强度和，所以直接将 dp 数组初始化为 $0$ 即可。

4. 遍历顺序。

由于求 $dp_{i,j}$ 牵连到了前 $i-1$ 个武器的最大强度，但 $dp_{i,j}$ 不会牵连到 $dp_{i,k}(k<j)$，所以 $i$ 需要按从小到大的顺序进行遍历，$j$ 哪个顺序遍历都行。

5. 打印 dp 数组。

按照 $dp$ 数组的含义，找到最小的一个 $q(1 \leq q \leq Q)$，使得 $dp_{n,q} \geq P$ 即可。若没有任何一个 $dp_{n,q} \geq P$，则直接按题意输出 -1 即可。

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int T, n, P, Q, p[109], c[109], dp[109][50009];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> T;
	while (T--) {
		cin >> n >> P >> Q;
		for (int i = 1; i <= n; i++)
			cin >> p[i] >> c[i];
		// 初始状态
		memset(dp, 0, sizeof(dp));
		// DP
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= Q; j++) {
				// 不买
				dp[i][j] = dp[i - 1][j];
				// 若可以买，就把买和不买取最大值
				if (c[i] <= j)
					dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i]] + p[i]);
			}
		}
		// 打印
		bool flag = true;
		for (int q = 1; q <= Q; q++) {
			if (dp[n][q] >= P) {
				cout << q << endl;
				flag = false;
				break;
			}
		}
		if (flag)
			cout << -1 << endl;
	}
	return 0;
}