poj1014 Dividing （多重背包）

转载请注明出处：http://blog.csdn.net/u012860063

题目链接：Mid-Central European Regional Contest 1999

大致题意：

有分别价值为1,2,3,4,5,6的6种物品，输入6个数字。表示对应价值的物品的数量，问一下能不能将物品分成两份，是两份的总价值相等。当中一个物品不能切开，仅仅能分给当中的某一方，当输入六个0是（即没有物品了），这程序结束。总物品的总个数不超过20000

输出：每一个測试用例占三行：

第一行： Collection #k: k为第几组測试用例

第二行：能否分（详细形式见用例）

第三行：空白（必须注意，否则PE）

#include <cstdio>
#include <iostream>
#define INF 100000000
using namespace std;int f[240005];  //f[j]相当于f[i][j]: 考虑1...i个物品。恰好放到容量为j。所能达到的最大价值
int v; //背包容量
int max(int a,int b)
{
if(a > b)
return a;
return b;
}
//处理一个全然背包 (该种物品不限量)
void complete_pack(int *a, int c, int w)
{
    for(int i = c; i <= v; i++)
        a[i] = max(a[i], a[i - c] + w);
}  //处理一个 01背包 (该种物品仅仅有一个)
void zeroone_pack(int *a, int c, int w)
{
    for(int i = v; i >= c; i--)
        a[i] = max(a[i], a[i - c] + w);
}  //处理一个多重背包 (该种物品指定上限)
void mutiple_pack(int *a, int c, int w, int m)
{
    //若该种物品足以塞满背包-->转化为全然背包
    if(c * m >= v)
{
        complete_pack(a, c, w);
        return;
    }    /*二进制思想拆分：多重背包中的一个物品--变成-->0-1背包中的多个物品
容量：2^0    2^1    2^2    2^k    m-∑前面             ***保证k达到最大值
价值：2^0*c  2^1*c  2^2*c  2^k*c  (m-∑前面 )*c
    */
    int k = 1;
    while(k <= m)
    {
        zeroone_pack(a, k * c, k * w);
        m = m - k;
        k = 2 * k;
    }
}  int main()
{
    //freopen("d:/data.in","r",stdin);
    //freopen("d:/data.out","w",stdout);
    int sum, i, c[7], w[7], m[7],cas = 0;
    while(scanf("%d%d%d%d%d%d", &m[1], &m[2], &m[3], &m[4], &m[5], &m[6]))
{
        if(m[1] == 0 && m[2] == 0 && m[3] == 0 && m[4] == 0 && m[5] == 0 && m[6] == 0)
break;
        sum = 0;
        for(i = 1; i <= 6; i++)
{
            c[i] = w[i] = i;
            sum += c[i] * m[i];
        }
        printf("Collection #%d:\n", ++cas);
        if(sum %2 == 1)
{
            printf("Can't be divided.\n\n");
        }
else
{
            sum /= 2;
            v = sum;
            for(i = 1; i <= sum; i++)
f[i] = -INF;
            f[0] = 0;              for(i = 1; i <= 6; i++)
mutiple_pack(f, c[i], w[i], m[i]);
            if(f[v] != v)//事实上仅仅要f[v]有正值就能够
{
                printf("Can't be divided.\n\n");
            }
else
{
                printf("Can be divided.\n\n");
            }
        }
    }
    return 0;
}