#include <cstdio>

int marbles[7];
int dp[60010];
bool status[60010];
int e[21];

int main() {
    //freopen("e:/data.txt", "r", stdin);
    e[1] = 1;
    for(int i = 2; i <= 20; ++i) {
        e[i] = e[i - 1] * 2;
    }

    int c = 1;
    while(true) {
        scanf("%d %d %d %d %d %d", &marbles[1], &marbles[2], &marbles[3], &marbles[4], &marbles[5], &marbles[6]);
        if(marbles[1] == 0 && marbles[2] == 0 && marbles[3] == 0 && marbles[4] == 0 && marbles[5] == 0 && marbles[6] == 0) {
            break;
        }

        printf("Collection #%d:\n", c++);

        int s = 0;
        for(int i = 1; i <= 6; ++i) {
            s += marbles[i] * i;
        }

        if(s & 1) {
            printf("Can't be divided.\n\n");
            continue;
        }

        int pack = s / 2;

        for(int i = 0; i <= pack; ++i) {
            dp[i] = 0;
            status[i] = false;
        }

        status[0] = true;

        int cur_value;
        for(int i = 1; i <= 6; ++i) {
            if(marbles[i] * i >= pack) {
                cur_value = i;
                for(int j = cur_value; j <= pack; ++j) {
                    if(status[j - cur_value] == true) {
                        dp[j] = dp[j] > dp[j - cur_value] + cur_value ? dp[j] : dp[j - cur_value] + cur_value;
                        status[j] = true;
                    }
                }
            } else {
                if(marbles[i] > 1) {
                    bool flag = true;
                    int k = 1;
                    int rest = marbles[i];

                    while(flag) {
                        if(e[k] > rest) {
                            cur_value = rest * i;
                            flag = false;
                        } else if(e[k] == rest){
                            cur_value = rest * i;
                            flag = false;
                        } else {
                            cur_value = e[k] * i;
                            rest -= e[k++];
                        }

                        for(int j = pack; j >= cur_value; --j) {
                            if(status[j - cur_value] == true) {
                                dp[j] = dp[j] > dp[j - cur_value] + cur_value ? dp[j] : dp[j - cur_value] + cur_value;
                                status[j] = true;
                            }
                        }
                    }
                } else if(marbles[i] == 1) {
                    cur_value = i;
                    for(int j = pack; j >= cur_value; --j) {
                        if(status[j - cur_value] == true) {
                            dp[j] = dp[j] > dp[j - cur_value] + cur_value ? dp[j] : dp[j - cur_value] + cur_value;
                            status[j] = true;
                        }
                    }
                }
            }
        }

        if(status[pack] == true && dp[pack] == pack) {
            printf("Can be divided.\n\n");
        } else {
            printf("Can't be divided.\n\n");
        }
    }

    return 0;
}

• Re:刚看完背包9讲之第3讲，照着写了写，贴出来献丑！ (730) DPkiller 2010-10-14 02:07:16