双塔DP。
dp[i][j]表示前i个物品，分成两堆（可以不全用），价值之差为j的时候，较小一堆的价值为dp[i][j]。
#include#include #include #include using namespace std;int dp[105][4000 + 10];int a[105];int n, sum;void read(){ for (int i = 1; i <= n; i++) scanf("%d", &a[i]);}void work(){ sum = 0; for (int i = 1; i <= n; i++) sum = sum + a[i]; memset(dp, -1, sizeof dp); int h; h = a[1]; dp[1][h + sum] = dp[1][0 - h + sum] = dp[1][sum] = 0; for (int i = 2; i <= n; i++) { h = a[i]; for (int j = 0; j <= sum*2; j++) dp[i][j] = dp[i - 1][j]; for (int j = 0; j <= sum*2; j++) { if (dp[i - 1][j] == -1) continue; int tmp = j - sum; if (tmp >= 0) { dp[i][h + tmp + sum] = max(dp[i][h + tmp + sum], dp[i - 1][j]); dp[i][tmp - h + sum] = max(dp[i][tmp - h + sum], dp[i - 1][j] + min(tmp, h)); } else if (tmp<0) { tmp = -tmp; dp[i][0 - (tmp + h) + sum] = max(dp[i][0 - (tmp + h) + sum], dp[i - 1][j]); dp[i][h - tmp + sum] = max(dp[i][h - tmp + sum], dp[i - 1][j] + min(tmp, h)); } } } int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, dp[i][sum]); if (ans == 0) printf("Sorry\n"); else printf("%d\n", ans);}int main(){ while (~scanf("%d", &n)) { read(); if (n < 0) break; if (n <=1) printf("Sorry\n"); else work(); } return 0;}