1.3 搬家3

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

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

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

数据输入

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

数据输出

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

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

数据范围

\(80\%\)的得分点，\(n\leq 12\)，\(v\) 及每个箱子的体积\(\leq 1000\)；其余 \(20\%\)的得分点，\(n\leq 100\)，\(v\) 及每个箱子的体积\(\leq 1000\)。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(){
    int n, v;
    int i;
    scanf("%d%d", &n, &v);
    for (i = 0; i < n; i++)
        scanf("%d", &w[i]);
    memset(dp, 0, sizeof(dp));
    for (i = 0; i < n; i++)//第i个箱子是否装车
    {   //当前剩余体积从v遍历到w[i]，保证所有可能性
        for (int j = v; j >= w[i]; j--)//第i个箱子不装车占用体积为dp[j]
        {   //第i个箱子装车占用体积为dp[j - w[i]] + w[i]，取两者之大
            dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
        }
    }
    printf("%d\n", v - dp[v]);//总体积去除占用最多的体积即为剩余体积
    return 0;
}

设计思路与复杂度分析

此题为经典0-1背包问题，注意区分此题与Moving2的区别，Moving2中\(n\leq 32\)可用折半枚举，而本题\(n\leq 100\)，折半枚举已经无可奈何了。

当然，上帝为你关上一扇门的时候必然为你开了另一扇窗。观察数据范围还可以发现，箱子体积才\(1000\)远小于Moving2，所以可以使用动态规划算法求解。

此题使用动态规划算法的时间复杂度为：\(O(nv)\)。

0%