HDU1171
题意
给n个物品, 然后后续n行, 每行两个数, v表示物品的价值, m表示物品的数量. 让你将物品分成尽可能接近的两堆. 多组输入, 当n<0时输入结束
1
2
3
0<n<=50
0<v<=50
0<m<=100
输出两个数A B, 中间以空格分开, 即分开的两堆的各自总价值, 要求A>=B
思路
思路有两个.
01背包, 这个不难想, 就是将物品根据数量继续拆分(就是将多组背包转化成01背包), 然后每个物品都设置其重量和价值相同, 然后设置一个大小为 sum/2 的背包, 进行01背包的计算. 最后 dp[sum/2] 就是所得两最接近的堆中的一堆, 答案就是 max(dp[sum/2],sum-dp[sum/2])
母函数, 这个是个母函数的模板题. 我们还是和01背包一样把相同的物品拆开, 然后对于每个物品, 都要么选, 要么不选. 也就是对于每个数, 都是 (1+x^v[i]) , 然后令母函数的最大项的次数是 sum/2 , 运算完成后, 从 sum/2 开始往0的方向找, 找到第一个系数不为0的项的次数, 就是所得两最接近的堆中的一堆, 和上个方法最后一步同样的处理可以得到答案.
另外, 对于母函数来说的话, 可以很方便的求出, 符合给定大小的背包的方法共有多少种.
代码
01背包
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
// 01背包
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int v[5050];
ll dp[505000];
int main() {
int n;
while (cin >> n && n >= 0) {
int pos = 0;
int sum = 0;
for (int i = 0; i < n; ++i) {
int tmp;
int num;
cin >> tmp >> num;
for (int j = 0; j < num; ++j) {
v[pos] = tmp;
++pos;
sum += tmp;
}
}
int V = sum / 2;
for (int i = 0; i <= V; ++i) {
dp[i] = 0;
}
for (int i = 0; i < pos; ++i) {
for (int j = V; j >= v[i]; --j) {
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
}
}
dp[V] = max(dp[V], sum - dp[V]);
cout << dp[V] << " " << sum - dp[V] << endl;
}
return 0;
}
母函数
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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int v[5050], start[5050], numEnd[5050];
int main() {
int n;
while (cin >> n && n >= 0) {
int pos = 0;
int sum = 0;
for (int i = 0; i < n; ++i) {
int tmp;
int num;
cin >> tmp >> num;
for (int j = 0; j < num; ++j) {
start[pos] = 0;
numEnd[pos] = 1;
v[pos] = tmp;
++pos;
sum += tmp;
}
}
int V = sum / 2;
// 最终要达到的数值,也就是次数的上限,p可以稍微大个1 2
int P = V;
// 实际上MAX = P+1即可
int MAX = P + 1;
// 项的个数
int factorNum = pos;
// 这两个数组其实开在这里不太好
int result[MAX], tmpResult[MAX];
// 虽然在这里一样,但是实际上可以把上面两个数组改成全局的,这里就可以起到优化效果了.
int sz = min((P + 1) * sizeof(int), sizeof(tmpResult));
memset(result, 0, sz);
result[0] = 1;
for (int i = 0; i < factorNum; ++i) { // 逐个括号处理
memset(tmpResult, 0, sz);
// 遍历括号内部的序列
for (int j = start[i]; j <= numEnd[i] && j * v[i] <= P; ++j) {
// 遍历reslut数组,和已有的结果相乘,得到新的结果.
for (int k = 0; k + j * v[i] <= P; ++k) {
tmpResult[k + v[i] * j] += result[k];
}
}
memcpy(result, tmpResult, sz);
}
int check_num = V;
while (check_num >= 0) {
if (result[check_num]) {
cout << max(sum - check_num, check_num) << " "
<< min(sum - check_num, check_num) << endl;
break;
}
--check_num;
}
}
return 0;
}
