poj - 1014 - Dividing(多重背包)

题意:价值为1,2,3,4,5,6的石子分别有n1,n2,n3,n4,n5,n6个,问能否把石子分成价值相等的两份(石子总个数 <= 20000)。

题目链接:http://poj.org/problem?id=1014

——>>转换为二进制拆分+01背包。。

二进制拆分:把第i种石子拆分成ni份,对于每一份,可取可不取,可用01背包,但这样时间开销较大。有这样一个事实:对于一个正整数n,小于等于n的任何一个正整数都可以用1, 2, 4, 8, 16, ..., 2^k, n-(2^(k+1)-1)中的几个数的和表示(想想n的二进制表示,小于等于n的正整数中,对于 <=2^k 的正整数,二进制位对应就是;对于 > 2^k 且 <= n 的正整数x,设前面的1 + 2 + 4 + 8 + 16 + ... + 2^k = s1, n-(2^(k+1)-1) = s2,则n = s1 + s2,则x = s1 + s2 - y,y是s1中某些数的和。),这样同样可以用01背包且时间开销减小了。。。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 20000 + 10;

int w[maxn], cnt, d[maxn*6];

void init() {
    cnt = 0;
}

void binary_split(int *a, int n) {
    for(int i = 1; i <= n; i++) {
        int sum = 0;
        for(int j = 1; sum+j <= a[i]; j <<= 1) {
            w[++cnt] = i * j;
            sum += j;
        }
        if(sum < a[i]) w[++cnt] = i * (a[i] - sum);
    }
}

bool dp(int sum) {
    memset(d, 0, sizeof(d));
    for(int i = 1; i <= cnt; i++) {
        for(int j = sum; j >= 0; j--)
            if(j >= w[i]) d[j] = max(d[j], d[j-w[i]] + w[i]);
    }
    return d[sum] == sum;
}

int main()
{
    int a[7], kase = 0;
    while(scanf("%d%d%d%d%d%d", a+1, a+2, a+3, a+4, a+5, a+6) == 6) {
        if(!a[1] && !a[2] && !a[3] && !a[4] && !a[5] && !a[6]) return 0;
        printf("Collection #%d:\n", ++kase);
        int sum = 0;
        for(int i = 1; i <= 6; i++) sum += i * a[i];
        if(sum&1) {
            puts("Can‘t be divided.\n");
        }
        else {
            init();
            binary_split(a, 6);
            dp(sum/2) ? puts("Can be divided.\n") : puts("Can‘t be divided.\n");
        }
    }
    return 0;
}


poj - 1014 - Dividing(多重背包)

上一篇:POJ 2449第K短路(A*+spfa)


下一篇:测试工具综合