链接
http://poj.org/problem?id=1014
题意
给你价值分别为
1
、
2
、
3
、
4
、
5
、
6
1、2、3、4、5、6
1、2、3、4、5、6的大理石
n
1
、
n
2
、
n
3
、
n
4
、
n
5
、
n
6
n_1、n_2、n_3、n_4、n_5、n_6
n1、n2、n3、n4、n5、n6份，数量和不超过
20000
20000
20000，现在问是否能把大理石分成价值相同的两份；
分析
这一题和
p
o
j
1742
poj1742
poj1742很像，首先考虑特殊情况，如果大理石价值总和为奇数，无论如何都不能分成相同两份，对于偶数的情况考虑多重背包；即第
i
i
i种物品有
n
i
n_i
ni个，价值为
i
i
i，每个物品可以选多次； 这时候背包的容量为价值总和
s
u
m
sum
sum也行，为
s
u
m
/
2
sum/2
sum/2也可以，在第
i
i
i阶段，
d
p
[
j
]
dp[j]
dp[j]表示前
i
i
i种硬币是否能拼成价值
j
j
j（所以它只有两种可能，要么为0要么为1，并且
d
p
[
0
]
=
1
dp[0]=1
dp[0]=1），我这里使用了二进制拆分将其转化为一个
01
01
01背包（不优化不知道能不能过），最后的时候看
d
p
[
s
u
m
/
2
]
dp[sum/2]
dp[sum/2]是否为1即可，需要注意的是这里没有类似求最大价值等最优问题，而是一个可行性问题；
代码
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991
typedef long long ll
;
namespace fastIO
{
inline int read() {
char c
= getchar(); int x
= 0, f
= 1;
while (c
< '0' || c
> '9') { if (c
== '-') f
= -1; c
= getchar(); }
while (c
>= '0' && c
<= '9') x
= x
* 10 + c
- '0', c
= getchar();
return x
* f
;
}
}
using namespace fastIO
;
using namespace std
;
int a
[8], dp
[5 * MAXN
], cnt
;
int main() {
while (cin
>> a
[1] >> a
[2] >> a
[3] >> a
[4] >> a
[5] >> a
[6]) {
int sum
= 0;
for (int i
= 1; i
<= 6; i
++)
sum
+= a
[i
] * i
;
if (sum
== 0)break;
printf("Collection #%d:\n", ++cnt
);
if (sum
% 2) {
printf("Can't be divided.\n\n");
continue;
}
memset(dp
, 0, sizeof(dp
));
dp
[0] = 1;
for (int i
= 1; i
<= 6; i
++) {
if (!a
[i
])continue;
int num
= min(a
[i
],sum
/ i
);
for (int j
= 1; num
> 0; j
<<= 1) {
if (j
> num
)j
= num
;
num
-= j
;
for (int k
= sum
; k
>= j
* i
; k
--)
dp
[k
] |= dp
[k
- j
* i
];
}
}
if (dp
[sum
/ 2])
cout
<< "Can be divided.\n" << endl
;
else cout
<< "Can't be divided.\n" << endl
;
}
}
