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%