背包问题
发布于2021-02-18
上次编辑2021-04-20
子集和问题
Introduction
对于整数集合 \(S\) 和给定的目标值 \(T\)，是否存在集合 \(U\subset S\)，使得 \(\sum_{a_i\in U} a_i=T\) 成立。
该问题已知是 NP 完全问题，该问题的一些变种已知也是 NP 完全问题：
- 集合中所有的整数为正
- 集合中的整数可正可负，并且 \(T=0\)
- 集合中所有的整数为正，并且 \(T=\frac{1}{2}\sum_{a_i\in S}a_i\)
子集和问题也可以看作是一类优化问题：找到子集和最接近 \(T\) 的子集。该问题是 NP 困难问题。
背包问题是子集和问题的推广形式。
指数时间复杂度算法
枚举
枚举 \(n\) 个元素的所有子集并判断子集和是否为目标值，该方法的时间复杂度为 \(\mathcal{O}(2^n\cdot n)\)，因为存在 \(2^n\) 个子集，并且最多求 \(n\) 个元素的和，空间复杂度为 \(n\)。
可以通过深度优先搜索来实现该算法，一些能够提高效率的方法如下：
- 以降序方式处理元素
- 如果某个结点的值超过了目前已找到的最佳子集的和，则对该结点剪枝
- 如果加上该结点和剩余结点的值，小于目前已找到的最佳子集的和，则对该结点剪枝
Horowitz and Sahni
Horowitz 和 Sahni 提出的算法的时间复杂度为 \(\mathcal{O}(2^{n/2}\cdot (n/2))\)，空间复杂度为 \(\mathcal{O}(2^{n/2})\)。
- 将 \(n\) 个元素分成大小为 \(n/2\) 的两个子集
- 存储两个子集的所有可能子集和，并且使得子集和数组有序
- 然后使用双指针来求解
1755. 最接近目标值的子序列和
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 | class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
auto gen_subset = [&] (int L, int R, vector<int> &result) {
result.emplace_back(0);
for (int i = L; i <= R; ++i) {
vector<int> tmp;
int j = 0, k = 0, n = result.size();
while (j < n && k < n) {
int a = result[j], b = result[k] + nums[i];
if (a <= b) tmp.emplace_back(a), ++j;
else tmp.emplace_back(b), ++k;
}
while (j < n) tmp.emplace_back(result[j++]);
while (k < n) tmp.emplace_back(result[k++] + nums[i]);
swap(result, tmp);
}
};
int n = nums.size(), m = n >> 1;
vector<int> left, right;
gen_subset(0, m - 1, left), gen_subset(m, n - 1, right);
int nl = left.size(), nr = right.size();
int i = 0, j = nr - 1;
int ans = abs(goal);
while (i < nl && j >= 0) {
int sum = left[i] + right[j];
ans = min(ans, abs(sum - goal));
if (sum == goal) break;
else if (sum > goal) --j;
else ++i;
}
return ans;
}
};
|
伪多项式时间动态规划
当集合中的所有元素为正，且目标值比较小时，可以使用动态规划求解。
用 \(\texttt{dp}[i - 1][j]\) 表示前 \(i\) 个元素能否得到和为 \(j\)，则加上第 \(i\) 个元素后能够得到 \(\texttt{dp}[i - 1][j + A[i]]\)，所以最后只需要判断 \(\texttt{dp}[n - 1][\texttt{target}]\) 就可以。从后往前遍历可以去掉第一维。
416. 分割等和子集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum & 1) return false;
int target = sum / 2;
vector<int> dp(target + 1);
dp[0] = 1;
for (auto x : nums) {
for (int i = target; i >= x; --i) {
dp[i] |= dp[i - x];
}
}
return dp[target];
}
};
|
k 进制有序子集生成
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | def k_base_subset(nums: List[int], K: int):
res = [0]
for x in nums:
Q = []
for i in range(K):
heapq.heappush(Q, (i * x, 0, i))
tmp, n = [], len(res)
while Q:
d, i, k = heapq.heappop(Q)
if i + 1 < n:
heapq.heappush(Q, (res[i + 1] + k * x, i + 1, k))
tmp.append(d)
res = tmp
return res
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | vector<int> k_base_subset(vector<int> &nums, int K) {
vector<int> res{0};
for (int x : nums) {
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> Q;
for (int i = 0; i < K; ++i) {
Q.emplace(i * x, 0, i);
}
vector<int> tmp;
int n = res.size();
while (!Q.empty()) {
auto [d, i, k] = Q.top(); Q.pop();
if (i + 1 < n) {
Q.emplace(res[i + 1] + k * x, i + 1, k);
}
tmp.emplace_back(d);
}
swap(res, tmp);
}
return res;
}
|
例题