hdu1059(多重背包)

时间：2023-03-09 22:08:11
hdu1059(多重背包)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1059

题意 : 按顺序读入一些列数，所对应的序列代表价值，数值代表个数(如a[5]=6 ，代表价值为五的钻石个 ), 通过计算判断这些钻石能否被平均分成二等分；

分析：已知正常多重背包复杂度为O((ΣN[i])V),这里(ΣN[i])<=120000,V<=60000;如果直接进行多重背包肯定超时。所以我们用二进制优化的多重背包。

这个复杂度为O（V*log((ΣN[i]))），优化了许多。。。至于原理背包九讲那里说得很清楚了。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 1000000007

#define inf 1<<30

#define N 100010

using namespace std;

int cnt[];

int dp[];

int main()

{

    int a[],cas=;

    while(scanf("%d",&a[])>)

    {

        int sum=a[];

        for(int i=;i<=;i++)scanf("%d",&a[i]),sum+=a[i]*i;

        if(sum==)break;

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

        if(sum%)

        {

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

        }

        memset(dp,,sizeof(dp));

        for(int i=;i<=a[];i++)dp[i]=;

        dp[]=;

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

        {

            if(!a[i])continue;

            int num=;

            for(int j=;j<=a[i];j*=)

            {

                cnt[num++]=i*j;

                a[i]-=j;

            }

            if(a[i]>)

            {

                cnt[num++]=a[i]*i;

            }

            for(int j=;j<num;j++)

            {

                for(int k=sum/;k>=cnt[j];k--)

                {

                        dp[k]=dp[k]||dp[k-cnt[j]];

                }

            }

        }

        if(dp[sum/]!=)puts("Can be divided.");

        else puts("Can't be divided.");

        puts("");

    }

}

还有种方法就是正常多重背包但是有技巧地剪枝，而且AC才78ms，前面二进制优化的多重背包要250ms

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 1000000007

#define inf 1<<30

#define N 100010

using namespace std;

int dp[];

int main()

{

    int a[],cas=;

    while(scanf("%d",&a[])>)

    {

        int sum=a[];

        for(int i=;i<=;i++)scanf("%d",&a[i]),sum+=a[i]*i;

        if(sum==)break;

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

        if(sum%)

        {

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

        }

        memset(dp,-,sizeof(dp));

        for(int i=;i<=a[];i++)dp[i]=;

        dp[]=;

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

        {

            if(!a[i])continue;

            for(int k=sum/;k>=;k--)

            {

                if(dp[k]==-)continue;

                for(int j=;j<=a[i]&&i*j+k<=sum/;j++)

                {

                    //这里剪枝最为关键，因为如果dp[i*j+k]=1后说明这个循环已经进行过一次了，没必要重复了

                    if(dp[i*j+k]!=-)break;

                    dp[i*j+k]=;

                }

            }

        }

        if(dp[sum/]!=-)puts("Can be divided.");

        else puts("Can't be divided.");

        puts("");

    }

}

相关文章