xindoo is
always here

hdoj 3732 Ahui Writes Word (多重背包)


      之前在做背包的题目时看到了这道题,一看,大喜,这不是裸裸的01背包吗!!  然后华丽丽的超时,相信很多人也和我一样没有考虑到数据量的大小。

      时隔多日,回过头来看这道题,依旧毫无头绪。。。。不过相比之前,我看到了更多细节。

      来看题目吧,可能有100000个单词,然后只有1000ms,但看包的大小,有10000,这样只能允许nlog(n)的算法,还有,每个单词的价值和花费都很小(不大于十),如果不考虑单词的不同,只考虑价值和花费只有最多100种东西,但如果把这些按多重背包的方法来计算依旧会超时,很容易想到和之前01背包的时间复杂度是一样的。

      还记得多重背包可以转换为01背包吗??我们不妨把这些物品进行打包,把每种物品分别1个、2个、4个…………(2^k)个进行打包,如果不足2^k个则单独打包,然后把每一包看做一件物品,继续使用01背包的方法进行计算,这样我们就把原来O(nc)的时间复杂度降到了O(clogn)。

//hdoj 3732
//2013-08-10-16.53
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int dp[10005];
int vc[11][11];
int w[10005];
int v[10005];

int main()
{
    int n, c;
    char s[100];
    while (scanf("%d %d", &n, &c) != EOF)
    {
        int a, b;
        memset(dp, 0, sizeof(dp));
        memset(vc, 0 ,sizeof(vc));
        for (int i = 1; i <= n; i++)
        {
            scanf("%s %d %d", &s, &a, &b);
            vc[a][b]++;
        }
        int cnt = 1;
        for (int i = 1; i <= 10; i++)
        {
            for (int j = 1; j <= 10; j++)
            {
                if (vc[i][j])
                {
                    int tmp = 1;
                    while (vc[i][j] > tmp)
                    {
                        w[cnt] = tmp*j;
                        v[cnt] = tmp*i;
                        vc[i][j] -= tmp;
                        cnt++;
                        tmp <<= 1;
                    }
                    w[cnt] = j*vc[i][j];
                    v[cnt] = i*vc[i][j];
                    cnt++;
                }
            }
        }
        for (int i = 1; i < cnt; i++)
        {
            for (int j = c; j >= w[i]; j--)
                dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
        printf("%d\n", dp[c]);
    }
    return 0;
}


      


打赏
未经允许不得转载:XINDOO » hdoj 3732 Ahui Writes Word (多重背包)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏