当前位置: 首页 > 工具软件 > diving > 使用案例 >

二进制优化DP Hdu1059-Diving

沃驰
2023-12-01

多重背包的复杂度为O(n * m * k),其中n为背包总容量,m为物品种类数,k为一种物品的数量。实际上等价于01背包。
二进制优化,是将一种物品的数量分解成1, 2, 4, 8, …, 2x, k-2x+1+1份并组成新的物品,注意除了最后一个数,其他数都是2的幂次。此时选择任意数量的该原物品,都可以等价表示成选择分解后的某几个新物品。选择新物品的任意组合,都可以表示成选择一定数量的原物品。于是转化为物品数目m * l o g 2 k log_2k log2k的01背包。因此复杂度为O(n * m * l o g 2 k log_2k log2k)。

题意

6种物品,权重为1到6,给出数量。求是否可能均分为两份权重相同的?

分析

显然这是一个多重背包,总容量是总权重值,物品容量是其权重。求dp[n/2]是否有解。普通多重背包会TLE,所以要用二进制优化,将6种物品分解成新的物品,转化为01背包

代码

// 二进制优化多重背包
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 20000;
bool dp[6*MAX_N+1];
int vals[6*MAX_N+1];
int main()
{
    int n[7];
    int k = 0;
    while (++k)
    {
        int sum = 0;
        int cnt = 0;
        for (int i = 1; i <= 6; i++)
        {
            scanf("%d", &n[i]);
            sum += i * n[i];
            // 将num个同类型物品捆绑为一个新物品
            // 可以用新物品的组合表示任意数量的原物品
            int num = 1;
            while (num <= n[i])
            {
                vals[cnt++] = num*i;
                n[i] -= num;
                num *= 2;
            }
            if (n[i] > 0) vals[cnt++] = i*n[i];
        }
        // 转化为01背包
        if (sum == 0) break;
        memset(dp, 0, sizeof(dp));
        dp[0] = true;
        for (int i = 0; i < cnt; i++)
            for (int j = sum; j >= vals[i]; j--)
                dp[j] |= dp[j-vals[i]];
        printf("Collection #%d:\n", k);
        if (sum % 2 == 0 && dp[sum/2] == true)
            printf("Can be divided.\n\n");
        else 
            printf("Can't be divided.\n\n");
    }
}
 类似资料: