蓝桥杯 盗墓分赃2

---

原题目链接

问题描述

在一个探险者的团队中，小明和小红是合作的盗墓贼。

他们成功盗取了一座古墓中的宝藏，包括 n 件不同重量的珍贵文物和黄金，第 i 件宝藏的重量为 ai。

现在，他们希望公平地分配这些宝藏，使得小明所分得的宝藏的总重量等于小红所分得的宝藏的总重量。

请检查是否存在这样的分配方案。需要注意的是，宝藏不能被分割成两半来调整重量，只能整个宝藏进行分配。

---

输入格式

• 第一行包含一个正整数 n，表示有 n 件宝藏。
• 接下来 n 行，第 i 行表示第 i 件宝藏的重量 ai。

---

输出格式

• 如果能公平分配输出 yes，否则输出 no。

---

样例输入

3
1
2
3

---

样例输出

yes

---

说明

样例中，将第 1 件和第 2 件宝藏分给小明，第 3 件宝藏分给小红，每人的宝藏重量都是 3。

---

评测数据规模

• 1 ≤ n ≤ 1000
• 1 ≤ ai ≤ 1000
• n ≤ sum(ai) ≤ 20000

---

c++代码

#include<bits/stdc++.h>using namespace std;int main() {int n, V = 0;cin >> n;vector<int> arr(n);for (int i = 0; i < n; i++) cin >> arr[i], V += arr[i];if (V % 2 != 0) { cout << "no"; return 0; }V /= 2;vector<int> last(V + 1), now(V + 1);for (int i = 0; i < n; i++) {for (int j = arr[i]; j <= V; j++) now[j] = max(last[j], arr[i] + last[j - arr[i]]);last = now;}if (last[V] == V) cout << "yes";else cout << "no";return 0;
}//by wqs

注意宝物要么归A，要么归B，不能放弃这个宝物。

---

📘 题目大意

给定一个包含 n 个元素的数组 a，数组中的第 i 个元素为 a[i]，表示第 i 件宝藏的重量。

总重量记为 all，要求判断是否可以从中选出若干个宝藏，使其总重量恰好为 all / 2。

---

🤔 解题思路

最初的思路可能是使用搜索，即每个数有“取”和“不取”两种状态，时间复杂度为 O(2^n)，显然在 n ≤ 1000 的范围内不可行。

进一步观察，这是一个典型的0-1背包问题，我们转化为如下模型：

• 背包容量：sum = all / 2（如果 all 是奇数，则不可能平分，直接输出 no）
• 每件物品的体积和价值：都等于宝藏重量 a[i]

我们希望判断是否存在一个子集，其元素之和正好等于 sum。

---

🧮 状态表示

定义状态数组：

dp[j] 表示总重量不超过 j 的情况下可以得到的最大重量。

初始条件：

dp[0] = 0，表示不选任何物品时重量为 0。

—in

🔁 状态转移方程

dp[j] = max(dp[j], dp[j - a[i]] + a[i])

遍历顺序： 为避免重复使用同一个物品，需要从大到小遍历 j（逆序遍历）。

---

✅ 判断条件

最终判断：

if dp[sum] == sum:输出 "yes"
else:输出 "no"

---

⏱️ 时间复杂度

• 时间复杂度：O(n × sum/2)，最多为 O(1000 × 10000) = 1e7，可以接受
• 空间复杂度：O(sum/2)，使用一维数组优化空间

---