多重背包的复杂度为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");
}
}