poj 1014 Dividing 多重背包之二进制优化

缘起

多重背包板题. poj 1014 Dividing

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
宝石的价值有6种,分别是1,2,3,4,5,6,然后给出每种宝石的数量(6个数,其总和不超过2万),
问你存不存在一种方案使得能够将这些宝石(注意，一块宝石不能分割)分成两部分,使得这两部分宝石的总价值相等?

【输入】
多样例. 每个样例就是6个数，分别表示六种宝石的数量. 宝石的总颗数<=2w. 以6个0结束.

【输出】
看样例输出

【样例输入】
1 0 1 2 0 0 
1 0 0 0 1 1 
0 0 0 0 0 0 

【样例输出】
Collection #1:
Can't be divided.

Collection #2:
Can be divided.

【限制】
1s

首先，讲解一下多重背包问题.

1
2
3
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费
的空间是Ci，价值是Wi。求解将哪些物品装入背包可使这些物品的耗费的空间
总和不超过背包容量，且价值总和最大。

和完全背包（【1】）相比，就是限制了每种物品的数量. 正是因为限制了每种物品的数量，所以解法就没有完全背包那么简单了. 一般的，有二进制优化和单调队列优化两种. 本文介绍二进制优化，至于单调队列优化后面会继续写文章.

二进制优化解法其实就是将多重背包问题转换为01背包. 即将Mi件物品并不是拆成1件一件的（那样转化成01背包的话时间复杂度太高）而是将Mi拆成二进制. 例如某件物品有13件, 则拆成1,2,4,8,6 这四件物品，而不是拆成13件. 一般的，M件物品拆成 1,2,…,2^{k-1}, M-2^k+1 这k件物品. 其中k是满足2^k<=M 的最大整数，在上述例子中, k=3

则如果我要取全部物品的话（即取13件），则只需要取1,2,4,6 这四件物品即可.

如果将多重背包一件一件的拆的话，复杂度就是 O(N*sigmaM)，而使用二进制优化之后，复杂度降为 O(N*sigma logMi), 这是巨大的进步.

有了上述思想，不难写下如下的多重背包算法的伪代码（很精美哦~相比单调队列O(NV)的优化，虽然复杂度略高，但是非常好写）

1
2
3
4
5
6
7
8
9
10
11
12
MultiplePack(F ,C, W ,M)
{
    if C · M ≥ V
    CompletePack(F,C,W)
    return
    k := 1
    while k < M
    ZeroOnePack(kC,kW )
    M := M − k
    k := 2k
    ZeroOnePack(C · M,W · M)
}

其中 F [i; v]表示前i种物品放入一个容量为v的背包的最大价值，当然，上面的算法可以将i滚动掉

回到本题——能不能等分价值. 首先将总价值计算出来. 然后如果价值为奇数，肯定是不能等分的. 如果是偶数的话，则计算出等分后一半的价值. 然后就是问，能不能用这些宝石中的一部分恰好组成这个价值. 则令

1
dp[i][j]为使用前i颗宝石, j价值能否达到.

即本题其实用的是多重背包的思想，而不是套多重背包的模板.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

const int maxn = 60005; // 宝石不超过2w颗, 所以价值不超过12w, 所以一半的价值不超过6w
bool dp[maxn]; // dp[i]表示价值i能否达到? 因为价值=重量, 所以可以这样优化
int n[7],sum; // 价值 1~6的宝石的数量

void zp(int c) // 01背包
{
	for (int i = sum; i>=c; i--)
	{
		dp[i] = dp[i] || dp[i-c];
	}
}

void cp(int c) // 完全背包
{
	for (int i = c; i<=sum; i++)
	{
		dp[i] = dp[i] || dp[i-c];
	}
}

void mp(int c, int m) // 多重背包
{
	if (c*m>=sum) // 如果等价于完全背包, 就运行完全背包算法
	{
		cp(c);
	}
	else // 二进制拆成01背包问题
	{
		int k = 1;
		while(k<m)
		{
			zp(k*c);
			m-=k;
			k<<=1;
		} // 最后 k>=m
		zp(m*c);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 1;
	while(scanf("%d%d%d%d%d%d", n+1, n+2, n+3, n+4, n+5, n+6), n[1]||n[2]||n[3]||n[4]||n[5]||n[6])
	{
		if (kase>1)
		{
			puts("");
		}
		printf("Collection #%d:\n", kase++);
		sum = n[1]+2*n[2]+3*n[3]+4*n[4]+5*n[5]+6*n[6];
		if (sum&1) // 如果价值总和是奇数,那就没什么好说的了
		{
			puts("Can't be divided.");
			continue;
		}
		sum>>=1;
		for (int i =0; i<=sum; i++) // 不取任何一件物品, 能否到达i价值?
		{
			dp[i] = !i;
		} // 初始化
		for (int i = 1; i<=6; i++)
		{
			mp(i,n[i]); // 每件物品进行多重背包
		}
		dp[sum]?puts("Can be divided."):puts("Can't be divided.");
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 148kB
Length 1282
Lang C++
Submitted 2019-08-28 19:22:16
Shared
RemoteRunId 20812992

参考

【1】https://yfsyfs.github.io/2019/08/19/poj-1384-Piggy-Bank-%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85/