1.2 搬家2

实验任务

小明的东西被打包成一个个箱子,他请了搬家公司,用一辆大卡车运箱子。小明有 \(n\) 个箱子,每个箱子有各自的体积,卡车有能装下的总体积上限。每件箱子要么装车要么不装,不能装一部分。

小明想在不超过总体积上限的前提下,尽可能装满卡车,也就是让卡车的剩 余空间最小。请你求出这个最小剩余空间。

数据输入

输入第一行为两个正整数 \(n\), \(v\),表示箱子的数量及总体积上限。接下去 \(n\) 个正整数,表示每个箱子的体积,以空格隔开。

数据输出

输出一个数,表示最小剩余空间。

输入示例 输出示例
3 11
3 7 3
1

数据范围

\(80\%\)的得分点,\(n\leq 12\)\(v\)及每个箱子的体积\(\leq 1000\);其余\(20\%\)的得分点,\(n\leq 32\)\(v\) 及每个箱子的体积\(\leq 10^9\)

源代码

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
#include <stdio.h>
#include <algorithm>
const int N = 16;
int n, V, x[N + N], i, j, left, right;
int a[1 << N], b[1 << N];

void bruteforce(int *d, int *x, int n) {
d[0] = 0;
d[1] = x[0]>V ? V + 1 : x[0];
for (i = 1; i<n; ++i) {
//第i个以后的物品都不放入背包时的所有情况已考虑
//前i-1个都已经考虑放与不放的所有情况,共2^i种情况
for (j = 0; j<(1 << i); ++j)
{ //现在考虑放第i个,只需要在前面的所有结果上加上x[i]即可
//总共2^i种情况,刚好和不放第i个的所有情况数一样
d[(1 << i) + j] = x[i] + d[j];
if (d[(1 << i) + j] > V) d[(1 << i) + j] = V + 1;
}
}
std::sort(d, d + (1 << n));
}

//折半枚举
int main() {
scanf("%d%d", &n, &V);
for (i = 0; i<n; ++i) scanf("%d", x + i);
left = n >> 1, right = n - left;
bruteforce(a, x, left);
bruteforce(b, x + left, right);
int ans = V;
//排序之后只需要a从小到大枚举的同时b从大到小枚举即可
for (i = 0, j = (1 << right) - 1; i<(1 << left); ++i) {
for (; ~j&&a[i] + b[j]>V; --j);
if (~j && (V - a[i] - b[j])<ans)
ans = V - a[i] - b[j];
}
printf("%d\n", ans);
return 0;
}

设计思路与复杂度分析

当问题的规模较大时,无法枚举所有元素的组合,但能够枚举一半元素的组合。此时可将问题拆成两半后分别枚举,再合并它们的结果。

本题中\(n\leq 32\)\(2^{32}\)数据范围太大,但是\(2^{16}\)却是一个可以接受的范围。所以考虑折半枚举算法。

本题为经典0-1背包问题,能够推导出动态规划的状态转移方程,但是由于\(v\)比较大,不能使用动态规划算法求解。注意与Moving3相区分。

两次枚举时间分别为\(O(2^{\frac n2})\),排序时间分别为\(O(n\times 2^{\frac n2-1})\),合并的时间为\(O(2^{\frac n2})\),所以总时间复杂度为:\(O(n\times 2^{\frac n2})\)

给博主加鸡腿!
0%