题目传送门
题意：
给你一堆硬币，让你分成两堆，分别给A，B两个人，求两人得到的最小差。
分析：
首先算出每个硬币的权值之和sum。然后以sum / 2为背包容量，求出能装出的最大包。答案就是sum - 最大包 * 2
原理：
如果刚好可以将硬币分为sum / 2和sum / 2那就最好了，答案直接是0。但如果分不到，那么其中一组的权值和肯定是sum / 2的前驱（也就是能凑出的最大的权值和且<=sum / 2）。所以，背包算出这个前驱即可。那么最小差就是另一组权值和 - 前驱 = sum - 前驱 * 2
AC代码：
#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <fstream>
#include <set>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define MAXN 50005
int w[MAXN];
int dp[MAXN];
int main() {
ios;int T;while (cin >> T) {
while (T--) {
memset(dp, 0, sizeof(dp));int n;cin >> n;int avg = 0;int sum = 0;for (int i = 1; i <= n; i++) {
cin >> w[i];sum += w[i];}avg = sum / 2;for (int i = 1; i <= n; i++) {
for (int j = avg; j >= w[i]; j--)dp[j] = max(dp[j], dp[j - w[i]] + w[i]);}cout << sum - 2 * dp[avg] << endl;}}return 0;
}