问题描述
在一个探险者的团队中，小明和小红是合作的盗墓贼。
他们成功盗取了一座古墓中的宝藏，包括 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)，使用一维数组优化空间