ACM: 562 – Dividing Coins

一直想學的背包問題，這題是0/1 Knapsack Problem。要把一堆面額不等的錢幣分成兩堆，使得兩堆錢幣總額的差距最小，輸出兩堆的差額。

在用Knapsack的做法之前還是先嘗試了一下greedy method，想看看在什麼情況greedy method會失敗。想法是：把錢幣由大排到小，從最大的開始，分給A、B，若A>B，就分給B，否則就分給A。這個做法在有些情況可以找到正確答案，但這個例子就不行：{50, 50, 49, 49, 48, 48, 2}。用這個做法會得到

A:{50, 49, 48, 2}
B:{50, 49, 48}

最小差距為2，但其實另一種分法就可以平分，A:{50, 49, 49}, B:{50, 48, 48, 2}，差距為0。

所以還是要用背包問題的DP做法，把錢幣盡量湊到總額的一半。

REFERENCES

良葛格學習筆記
演算法筆記

CODE

#include <iostream>

using namespace std;

enum { MAX_M = 100, MAX_VAL = 500, MAX_SUM = MAX_VAL*MAX_M };

int main(){

    int n, m, c[MAX_M];

    int i, j, t, sum, half, p[MAX_SUM+1] = {};

    scanf("%d", &n);

    for(; n>0; --n){

        scanf("%d", &m);

        sum = 0;

        for(i=0; i<m; ++i){

            scanf("%d", &c[i]);

            sum += c[i];

        }

        half = sum / 2;

        for(i=0; i<m; ++i) //all coins

            for(j=half; j>=c[i]; --j)

                p[j] = max(p[j], p[j-c[i]]+c[i]);

        cout << (((t = 2 * p[half] - sum) > 0) ? t : -1*t ) << endl;

        memset(p, 0, sizeof(p));

    }//n inputs

    return 0;

}