UVa 10032. Tug of War

Description

N個人參加拔河比賽，每個人有其重量w[i]，欲使二隊的人數最多只差一，雙方的重量和越接近越好。請問二隊的重量和分別是多少？

Input Format

第一列有一個整數，代表以下有幾組測試資料。每筆測試資料的第1列有一個整數 n$(n\le100)$，代表共有n個人參加拔河。
接下來的n列，代表這n個人的體重，體重均界於1到450之間。測試資料間有空一列。請參考Sample Input。

Output Format

每一筆測試資料請輸出一列，包含2個整數，代表2隊的總體重。如果這2個數不相同，小的在前面。測試資料間有空一列。請參考Sample Output。

Sample Input

1

3
100
90
200

Sample Output

190 200

UVa - 10032
翻譯來源：Luckycat

Solution

這題可以用一般的DP解，令bool dp[i][k]代表 是否可以在選擇$k$人時，其重量總和為$i$ ，如果是這樣解的話，時間複雜度會到$O(n^2 \times \text{sum-of-weight})$，所以以最大測資來看需要計算$100^2 \times 17500 = 1.75 \times 10^8$次，很明顯地會TLE，所以這時候就要用位元運算來簡化。
首先我們令long long int dp[i]代表 當重量為$i$時，有哪些人數可以達成 。
假設dp[5] = 0b001010; (0b是使用二進位的表示方法)，代表可以選擇1和3人使其重量和為5。詳細解法請看Code。
時間複雜度$O(n^2 + \text{sum-of-weight})$

Code

/*************************************************************************
  > File Name: 10032 - Tug of War.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Wed Feb 14 19:23:28 2018
*************************************************************************/

#include <iostream>
using namespace std;

long long dp[22600];
int input[110];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int c, n, sum, Sh, Nh;
    cin >> c;
    while (c--) {
        cin >> n;
        sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> input[i];
            sum += input[i];
        }
        Sh = sum >> 1;
        Nh = (n + 1) >> 1;
        for (int i = 1; i <= Sh; i++)
            dp[i] = 0;
        dp[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = Sh; j >= input[i]; j--)
                dp[j] |= dp[j - input[i]] << 1LL;
        for (int i = Sh; i >= 0; i--)
            if (dp[i] >> Nh & 1 || ((n & 1) && (dp[i] >> (Nh - 1) & 1))) {
                cout << i << ' ' << sum - i << '\n';
                break;
            }
        if (c)
            cout << '\n';
    }
}