题意

洛谷 P1466 集合 Subset Sums

将1到N的整数分成两个和相同的集合,问有多少种分法?

分析

这道题其实是一道标准的经典DP(只要正确建模)。结果我一看数据范围只有39,第一反应是写了一个Meet-in-the-Middle出来。当然也不是不行……

DP的做法是这样的:把原问题换成,用1到N的整数之和表示某个数字,最多有多少种表示方法?然后思路就很简单了,用f[i][j]表示用前i个整数表示j的方法,f[i][j] = f[i-1][j] + f[i-1][j-i]

然后我才意识到对N大小的限制主要是为了动态规划的其中一维不要太大……

代码

DP

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
/*
ID: zhanghu15
TASK: subset
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;
typedef long long int LL;

int N;
LL f[40][8000];

int main() {
ofstream fout("subset.out");
ifstream fin("subset.in");
fin >> N;
int sum = N * (N + 1) / 2;
if (sum % 2 != 0) {
fout << 0 << endl;
return 0;
}
f[0][0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 8000; j++) {
f[i][j] = f[i-1][j];
if (j >= i)
f[i][j] += f[i-1][j-i];
}
}
fout << f[N][sum / 2] / 2 << endl;
return 0;
}

Meet-in-the-Middle

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
/*
ID: zhanghu15
TASK: subset
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;
typedef long long int LL;

int main() {
ofstream fout("subset.out");
ifstream fin("subset.in");
int N;
fin >> N;
int sum = N * (N + 1) / 2;
if (sum % 2 != 0) {
fout << 0 << endl;
return 0;
}
int halfSum = sum / 2;
int halfN = N / 2;
// Meet-in-the-Middle
map<int, int> cntMap;
// gather [1, halfN] sums
for (int i = 0; i < (1 << halfN); i++) {
int sum = 0;
for (int j = 0; j < halfN; j++)
if (i & (1 << j))
sum += j + 1;
// cout << i << ' ' << sum << endl;
cntMap[sum]++;
}
// gather [halfN+1, N] sums
LL ans = 0; // 注意数据范围……
for (int i = 0; i < (1 << (N - halfN)); i++) {
int sum = 0;
for (int j = 0; j < N - halfN; j++)
if (i & (1 << j))
sum += j + halfN + 1;
if (cntMap.find(halfSum - sum) != cntMap.end()) {
ans += cntMap[halfSum - sum];
}
}
fout << ans / 2 << endl;
return 0;
}

题目来源:https://leetcode.com/problems/tallest-billboard/description/

标记难度:Hard

提交次数:1/2

代码效率:

  • 动态规划:136ms
  • 中间相遇:184ms

题意

给定<=20根棍子,要求从中拿出一些,分成两组,使得每组的棍子长度之和相等。保证所有棍子的长度之和最大是5000。

分析

在比赛的时候我能想到的最好的解法是这样的:

  • 枚举第一组都有哪些棍子(2^20
  • 对于剩下的棍子,用动态规划的方法判断能否组成第一组已有的长度(5000*20

显然这个算法是会超时的。但是也许它已经接近正解了。


解法1:-1,0,1背包

把这个问题看成是扩展版的01背包问题:对于每根棍子,我们可以把它加入背包中,不加入背包中,还可以把它从背包中减去。

f[i][j]表示用前i根棍子能否组成和为j的长度(j有可能是负的)。则f[i+1][j] = f[i][j] || f[i][j-rods[i+1]] || f[i][j+rods[i+1]]。为了找到可能的最大长度,用辅助数组g[i][j]记录f[i][j]为真时,最大可能的正长度之和。算法的复杂度为O(10000*N)[1]

解法2:中间相遇法

rods数组分成大致相等的两半,然后对每一半都枚举每根棍子是+,-还是0。然后对于左边的一半得到的和,在右边寻找这个和的负值是否存在。最后取最大值。算法复杂度为O(3^(N/2))

这个算法也需要记录最大可能的正长度之和。

代码

解法1:扩展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
36
37
38
39
40
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
bool f[20][10001]; // f[i][j+5000](index负数的一种方法)
int g[20][10001];
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
int ans = 0;
for (int i = 0; i < rods.size(); i++) {
f[i][5000] = true;
for (int j1 = 0; j1 <= 10000; j1++) {
int j = j1 - 5000; // j才是真正的j,j1是j+5000
if (i == 0) {
if (j == rods[i]) {
f[i][j1] = true;
g[i][j1] = rods[i];
}
if (j == -rods[i]) f[i][j1] = true;
}
else {
// 三种情况:分别更新g,找到最大值
if (f[i-1][j1]) {
f[i][j1] = true;
g[i][j1] = max(g[i][j1], g[i-1][j1]);
}
if (j1 >= rods[i] && f[i-1][j1-rods[i]]) {
f[i][j1] = true;
g[i][j1] = max(g[i][j1], g[i-1][j1-rods[i]] + rods[i]);
}
if (j1 + rods[i] <= 10000 && f[i-1][j1+rods[i]]) {
f[i][j1] = true;
g[i][j1] = max(g[i][j1], g[i-1][j1+rods[i]]);
}
}
}
ans = max(ans, g[i][5000]);
}
return ans;
}
};

解法2:中间相遇法

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
class Solution {
private:
unordered_map<int, int> results; // 和 - 最大正值和
int M, N;
int ans;

// 枚举棍子状态:sum是和,p是正值和
void dfs(int x, int sum, int p, vector<int>& rods, bool check) {
if (x >= rods.size()) {
if (!check) results[sum] = max(results[sum], p);
else {
if (results.find(-sum) != results.end())
ans = max(ans, results[-sum] + p);
}
return;
}
dfs(x+1, sum, p, rods, check);
dfs(x+1, sum+rods[x], p+rods[x], rods, check);
dfs(x+1, sum-rods[x], p, rods, check);
}

public:
int tallestBillboard(vector<int>& rods) {
N = rods.size();
if (N == 0) return 0;
M = N / 2;
vector<int> rod1, rod2;
for (int i = 0; i < M; i++)
rod1.push_back(rods[i]);
for (int i = M; i < N; i++)
rod2.push_back(rods[i]);
ans = 0;
dfs(0, 0, 0, rod1, false);
dfs(0, 0, 0, rod2, true);
return ans;
}
};

  1. wangzi6147's Solution for LeetCode 956 - Java knapsack O(N*sum)