本题是一道典型的可行性多重背包问题，问题非常经典，如果是刚刚学习背包问题解法那就不应错过。
已知有一些大小不一的弹珠，根据未知标准划定了它们的价值，分别定位 6 个档次，故而可以将每个弹珠的价值记为 1 到 6 的正整数。假设要将一堆弹珠分给两个人，使得两人分得的弹珠的总价值相等。已知弹珠堆中所有不同档次的弹珠有多少个，问是否存在这样公平的分配方法。
本题有多组输入数据，每组数据为一行，每行有 6 个数字，以空格分开，表示从 1 到 6 的不同价值的弹珠的数量。如果 6 个数字都为 0 则表示输入结束，数字最大为 20000。
示例输入为：
1
2
3
| 1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
|
根据对应输入，输出能否均分这些弹珠。要注意输出数据必须符合格式。
对应的示例输出为：
1
2
3
4
5
| Collection #1:
Can't be divided.
Collection #2:
Can be divided.
|
可以参考 poj1011 Sticks 中的解析理解。
可以参考 背包问题学习之多重背包 理解。
本题实际上需要求出所有弹珠的价值总和，如果它是技术则一定无法均分，是偶数则要寻找可行的分配方法。
最基本的方法就是将输入提供的各个弹珠做树的节点，然后使用深度优先搜索的办法，搜索是否有路径，符合所有节点的包含的弹珠价值和等于总价值和的一半。因为本题数据规模不大，而且一旦有符合条件的路径就可以停止搜索，所以使用搜索方法也不会太慢。
另一种方法就是采用可行性多重背包问题的通用解法，求给定的弹珠集合中是否能取出一些弹珠凑出总价值和的一半。当然，使用“二进制分隔法”求解多重背包也可以。
本题数据规模不大，各个解法之间的差异也很小。
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
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.System.in;
public class Main {
private static int buf[] = new int[6];
private static int total;
private static boolean divided;
private static void dfs(int value, int number) {
if (divided) return;
if (value == total / 2) {
divided = true;
return;
}
for (int i = number; i >= 1; i--) {
if (buf[i - 1] != 0) {
if (value + i <= total / 2) {
buf[i - 1]--;
dfs(value + i, i);
if (divided) break;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(in));
int index = 1;
while (true) {
String[] strings = reader.readLine()
.split(" ");
total = 0;
for (int i = 0; i < 6; i++) {
buf[i] = Integer.parseInt(strings[i]);
total += buf[i] * (i + 1);
}
if (total == 0) break;
divided = false;
if (total % 2 == 0) {
dfs(0, 6);
}
System.out.printf("Collection #%d:\n", index++);
if (divided) {
System.out.print("Can");
} else {
System.out.print("Can't");
}
System.out.println(" be divided.");
System.out.println();
}
}
}
|
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
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.System.in;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(in));
int index = 1;
int total = 0;
boolean divided;
while (true) {
String[] strings = reader.readLine()
.split(" ");
total = 0;
int[] buf = new int[6];
for (int i = 0; i < 6; i++) {
buf[i] = Integer.parseInt(strings[i]);
total += buf[i] * (i + 1);
}
if (total == 0) break;
divided = false;
if (total % 2 == 0) {
total /= 2;
int[] dp = new int[total + 1];
for (int i = 1; i <= total; i++) dp[i] = -1;
dp[0] = 0;
for (int i = 1; i <= 6; i++) {
for (int j = 0; j <= total; j++) {
if (dp[j] >= 0) {
dp[j] = buf[i - 1];
} else {
dp[j] = (j < i || dp[j - i] <= 0) ? -1 : dp[j - i] - 1;
}
}
}
if (dp[total] >= 0) divided = true;
}
System.out.printf("Collection #%d:\n", index++);
if (divided) {
System.out.print("Can");
} else {
System.out.print("Can't");
}
System.out.println(" be divided.");
System.out.println();
}
}
}
|
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.System.in;
public class Main {
private static int total;
private static int[] dp;
private static boolean divided;
private static int max(int a, int b) {
return a > b ? a : b;
}
private static void zeroOnePAck(int size, int value) {
for (int i = total; i >= size; i--) {
dp[i] = max(dp[i], dp[i - size] + value);
if (dp[i] == total) {
divided = true;
break;
}
}
}
private static void completePack(int size, int value) {
for (int i = size; i <= total; i++) {
dp[i] = max(dp[i], dp[i - size] + value);
if (dp[i] == total) {
divided = true;
break;
}
}
}
private static void multiplePack(int size, int value, int amount) {
if (size * amount >= total) {
completePack(size, value);
return;
}
if (divided) return;
for (int i = 1; i < amount; i *= 2) {
zeroOnePAck(i * size, i * value);
if (divided) return;
amount -= i;
}
zeroOnePAck(amount * size, amount * value);
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(in));
int index = 1;
while (true) {
String line = reader.readLine();
String[] strings = line.split(" ");
int[] buf = new int[6];
total = 0;
for (int i = 0; i < 6; i++) {
buf[i] = Integer.parseInt(strings[i]);
total += (i + 1) * buf[i];
}
if (total == 0) break;
divided = false;
if (total % 2 == 0) {
total /= 2;
dp = new int[total + 1];
for (int i = 1; i <= total; i++) {
dp[i] = Integer.MIN_VALUE;
}
dp[0] = 0;
for (int i = 1; i <= 6; i++) {
multiplePack(i, i, buf[i - 1]);
if (divided) break;
}
}
System.out.printf("Collection #%d:\n", index++);
if (divided) {
System.out.print("Can");
} else {
System.out.print("Can't");
}
System.out.println(" be divided.");
System.out.println();
}
}
}
|