poj1014 hdu1059 Dividing 多重背包

有价值为1~6的宝物各num[i]个，求能否分成价值相等的两部分。

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#define inf 0x3f3f3f3f

#define ll long long

#define mod 1000000007

using namespace std;

int dp[120010],num[10],v;

void pack01(int c,int w)

{

    for(int i=v;i>=c;i--)

        dp[i]=max(dp[i],dp[i-c]+w);

}

void packall(int c,int w)

{

    for(int i=c;i<=v;i++)

        dp[i]=max(dp[i],dp[i-c]+w);

}

void mulpack(int c,int w,int n)

{

    if(c*n>=v)

        packall(c,w);

    else

    {

        int i=1;

        while(i<n)

        {

            pack01(c*i,w*i);

            n-=i;

            i+=i;

        }

        pack01(c*n,w*n);

    }

}

int main()

{

    int cas=1,i,j,sum;//在这里多定义了一个v 导致一直出不来例子

    while(1)

    {

        sum=0;

        for(i=1;i<=6;i++)

        {

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

            sum+=(num[i]*i);//WA

        }

        if(sum==0) break;

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

        if(sum&1)

        {

            printf("Can't be divided.\n\n");

            continue;

        }

        memset(dp,0,sizeof dp);

        v=sum/2;

        for(i=1;i<=6;i++)

            if(num[i]) mulpack(i,i,num[i]);

        if(dp[v]==v) printf("Can be divided.\n\n");

        else printf("Can't be divided.\n\n");

    }

    return 0;

}