渣银选手来答一发。这题有一个分组背包的思路，请看下面的表： . . . . . ... ... ... 假设答案为 那么它等价于 相信聪明的你已经发现了，如果答案存在，则存在从上面的表的每一列选择一个数字，它们的和为 0。所以这就变成了一个简单的分组背包的问题了。当然实现时需要避开一个小bug，也就是上面的表全选0的情况，还有，统计和的时候也得想想办法。anyway，这是我的代码： # include <bits/stdc++.h> using namespace std; const int N = 100 + 5; const int M = 2000 + 5; bool dp[N][3][M * 4]; //dp[i][0/1/2][j] = (0/1) 表示前i个里面(0: 选择+a[i] 1: 选择-a[i] 2: 不选第i个数字)之后是否能凑成总和j int sum[N][3][M * 4]; //记录一下路径上正数的和，便于统计答案 int a[N]; int f(int x) //因为可能出现负数下标，所以做这个处理 { return x + 4000; } int main () { int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; dp[0][2][f(0)] = true; for (int i = 0; i < n; ++i) { for (int j = 0; j <= 2; ++j) { for (int k = f(-2000); k <= f(2000); ++k) { if (dp[i][j][k] == false) continue; dp[i+1][0][k + a[i+1]] = true; sum[i+1][0][k + a[i+1]] = max(sum[i+1][0][k + a[i+1]], sum[i][j][k] + a[i+1]); dp[i+1][1][k - a[i+1]] = true; sum[i+1][1][k - a[i+1]] = max(sum[i+1][1][k - a[i+1]], sum[i][j][k]); dp[i+1][2][k] = true; sum[i+1][2][k] = max(sum[i+1][2][k], sum[i][j][k]); } } } for (int i = 0; i <= 2; ++i) { if (dp[n][i][f(0)] == true && sum[n][i][f(0)] != 0) { // 之所以 sum[n][i][f(0)] != 0 是为了排除全都不选的特殊情况 cout << sum[n][i][f(0)]; return 0; } } cout << "Impossible" << endl; return 0; } 看懂点个赞哈~