`
fulerbakesi
  • 浏览: 559296 次
文章分类
社区版块
存档分类
最新评论

HDU 1059 Dividing(多重背包)

 
阅读更多

题目链接:Click here~~

题意:

有价值为1~6的珠宝,每种价值的珠宝数量已经给出,问是否可以将价值平分。

解题思路:

又是一道平分问题,于是可以将问题转化为容量为 sum/2 的背包问题(sum为总价值)。

对于每种价值的物品 i ,是一个费用为 i ,价值为 i ,数量为num[i]的多重背包。

还用到了多重背包常用的二进制优化。

方法是:将第 i 种物品分成若干件物品替换以后的物品,其中,每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。

我们使这些系数分别为1,2,4,…,2^(k-1),num[i]-2^k+1,且k是满足num[i]-2^k+1>0的最大整数。

比如,num[i]为14,就将这种物品分为系数为1,2,4,7的四件物品。

如此,复杂度为O(n*∑log num[i]),优化了很多。

另外,当背包容量V很大(10^6),num[i]比较小(10^2)时,还可以用搜索做这类平分问题,下一篇会给出。

代码很好实现。下面是我写的,不算精简。

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;

#define CLR(a,v) memset(a,v,sizeof(a))

int num[7],dp[60010];
int dig[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};

int main()
{
    int v,ncase = 0;
    while(1)
    {
        int  sum = 0;
        for(int i=1;i<=6;i++)
        {
            scanf("%d",&num[i]);
            sum += i*num[i];
        }
        if(sum == 0)
            break;
        printf("Collection #%d:\n",++ncase);
        if(sum&1)
        {
            printf("Can't be divided.\n\n");
            continue;
        }
        CLR(dp,0);
        sum /= 2;
        for(int i=1;i<=6;i++)
        {
            for(int d=0;num[i];d++)
            {
                if(num[i] >= dig[d])
                {
                    v = i*dig[d];
                    num[i] -= dig[d];
                }
                else
                {
                    v = i*num[i];
                    num[i] = 0;
                }
                for(int j=sum;j>=v;j--)
                    dp[j] = max(dp[j],dp[j-v]+v);
            }
        }
        if(dp[sum] == sum)
            printf("Can be divided.\n\n");
        else
            printf("Can't be divided.\n\n");
    }
    return 0;
}

从风神博客中抄了个模板,挺清楚的。

#include <stdio.h>
#include <string.h>
#define N 60006
#define max(a,b) a > b ? a : b
int V,num[7],dp[N];

void Bag_01(int c,int w)
{
    for(int i=V;i>=c;i--)
        dp[i] = max(dp[i],dp[i-c]+w);
}

void Bag_All(int c,int w)
{
    for(int i=c;i<=V;i++)
        dp[i] = max(dp[i],dp[i-c]+w);
}

void Bag_Multiple(int c,int w,int num)
{
    if(c*num >= V)
    {
        Bag_All(c,w);
        return ;
    }
    int k = 1;
    while(k < num)
    {
        Bag_01(c*k,w*k);
        num -= k;
        k <<= 1;
    }
    Bag_01(c*num,w*num);
}
int main()
{
    int v,ncase = 0;
    while(1)
    {
        int  sum = 0;
        for(int i=1;i<=6;i++)
        {
            scanf("%d",&num[i]);
            sum += i*num[i];
        }
        if(sum == 0)
            break;
        printf("Collection #%d:\n",++ncase);
        if(sum&1)
        {
            printf("Can't be divided.\n\n");
            continue;
        }
        memset(dp,0,sizeof(dp));
        V = sum/2;
        for(int i=1;i<=6;i++)
            Bag_Multiple(i,i,num[i]);
        if(dp[V] == V)
            printf("Can be divided.\n\n");
        else
            printf("Can't be divided.\n\n");
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics