POJ 1014 dividing

分析：

如果想要公平的分得彈球，那麼彈球的價值總和一定是偶數，可以先進行判斷彈球的價值總和，若是奇數則不需要做下面的判斷。

如果是偶數，我們可以把這個問題映射為多重背包問題，並且這個背包是要求完全裝滿的。背包的總容量V就是所有彈球總價值和sum的一半，彈球的cost和weight都是其編號。個數則是由外界輸入的。最後進行判斷：如果得到的F[V]確定的等於sum/2，則說明能夠公平的分彈球。

需要注意的是，由於彈球最大個數是20000，所以極端情況是20000個彈球都是放在了價值為6的位置上，這樣，V的最大值就是6*20000/2+1=60001。

好了，翠花，上代碼：

[cpp]
#include <iostream>  
using namespace std; 
 
#define LEN 7  
#define INIT 0xffffffff  
int F[60001]; 
 
int max(int x, int y) 
{ 
    return x>y?x:y; 
} 
 
void ZeroOnePack(int cost, int weight, int V) 
{ 
    for (int v=V; v>=cost; --v) { 
        F[v] = max(F[v], F[v-cost]+weight); 
    } 
} 
 
void CompletePack(int cost, int weight, int V) 
{ 
    for (int v=cost; v<=V; ++v) { 
        F[v] = max(F[v], F[v-cost]+weight); 
    } 
} 
 
void MultiPack(int cost, int weight, int V, int amount) 
{ 
    if (cost*amount>=V) { 
        CompletePack(cost, weight, V); 
        return; 
    } 
    int k = 1; 
    while (k<amount) { 
        ZeroOnePack(cost*k, weight*k, V); 
        amount -= k; 
        k *=2; 
    } 
    ZeroOnePack(cost*amount, weight*amount, V); 
} 
 
int main(int argc, char **argv) 
{ 
    int index = 0; 
    int num[LEN]; 
    while (1) { 
        ++index; 
        int sum = 0; 
        int bin = 0; 
        for (int i=1; i<LEN; ++i) { 
            cin>>num[i]; 
            sum += i * num[i]; 
            bin |= num[i]; 
        } 
        if (!bin) 
            break; 
        if (sum&0x01) 
            cout<<"Collection #"<<index<<":\n"<<"Can't be divided."<<endl<<endl; 
        else { 
            int V = sum>>1; 
            F[0] = 0; 
            for (int i=1; i<=V; ++i) 
                F[i] = INIT; 
            for (int i=1; i<LEN; ++i) 
                MultiPack(i, i, V, num[i]); 
            if(F[V]!=V) 
                cout<<"Collection #"<<index<<":\n"<<"Can't be divided."<<endl<<endl; 
            else 
                cout<<"Collection #"<<index<<":\n"<<"Can be divided."<<endl<<endl; 
        } 
    } 
    system("pause"); 
    return 0; 
}