UVa 1125 - Sherlock Holmes

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

有 N 個箱子，每個箱子都有 M 顆球，每一個箱子的黑、白球分配的個數不同，希望分成兩堆，每一堆必須有 N/2 個箱子，並且要符合黑球、或白球必須在兩堆佔有多數 (> 50%) 的情況。

假設佔有的比例分別為 m1, m2，最大化 min(m1, m2)。

Sample Input

4 
30 
17 13
12 18
20 10
14 16

Sample Output

W 51.67

Solution

N 很大，M 也很大。一開始就目測需要 random 的隨機交換法，這樣湊出答案的機率是挺高的。

當然這有點不靠譜，使用 dp 背包問題，由於狀態數量太多，必須使用 set 壓縮。

dp[i][j] 表示放置前 i 個箱子，存在 j 個數的球。

統計兩色的球總個數，個數多的必然是最後佔有多數，決定球顏色後，針對個數進行背包問題的計算，由於每個箱子的球總數一樣，分成兩堆時，分母是固定的，因此可以無視另一個顏色的存在。

#include <stdio.h>
#include <stdlib.h> 
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int n, m, A[32767];
    while (scanf("%d %d", &n, &m) == 2) {
        int w, b, wsum = 0, bsum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &w, &b);
            wsum += w, bsum += b;
            A[i] = w;
        }
        if (wsum == bsum || n%2 != 0) {
            puts("No solution");
            continue;
        }
        char major = 'W';
        if (wsum < bsum) {
            major = 'B';
            wsum = bsum;
            for (int i = 0; i < n; i++)
                A[i] = m - A[i];
        }
        set<int> dp[32767];
        set<int>::iterator it;
        dp[0].insert(0);
        for (int i = 0; i < n; i++) {
            int w = A[i];
            for (int j = min(i, n/2 - 1); j >= 0; j--) {
                for (it = dp[j].begin(); it != dp[j].end(); it++)
                    dp[j+1].insert((*it) + w);
            }
        }
        
        int ret = -1;
        int half = n/2 * m / 2;
        for (it = dp[n/2].begin(); it != dp[n/2].end(); it++) {
            if (*it <= wsum/2 && *it > half)
                ret = max(ret, *it);
        }
        if (ret < 0) {
            puts("No solution");
        } else {
            printf("%c %.2lf\n", major, ret * 100.0 / (n/2 * m));
        }
    }
    return 0;
}