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%