当前位置： 首页 > web >正文

【背包dp----01背包】例题1------[NOIP2001]装箱问题（简化的01背包）

web 2025/5/8 23:49:32

例1： [NOIP2001]装箱问题

（题目链接：https://ac.nowcoder.com/acm/contest/24213/1017）

题目描述

有一个箱子容量为V（正整数，0 ≤ V ≤ 20000），同时有n个物品（0＜n ≤ 30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述:

1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积

输出描述:

1个整数，表示箱子剩余空间。

示例1

输入

24
6
8
3
12
7
9
7

输出

0

题解：二维dp（二维dp数组）

一、题目理解

我们要找一种方法，通过选择若干个物品放入给定体积的箱子中，使得剩余的空间尽可能小。即最大化使用的空间。

  • 每一步可以选择放或不放当前物品。
  • 所以我们需要找出所有可能的选择中，使用空间最大的那一种。

原问题抽象成：前n个物品中，任取若干个装入箱内，尽可能的填满体积为vs(输入的体积)的箱子

最终结果通过vs减去最优解得到

二、状态定义

设 dp[i][j] 表示从前 i 个物品中选择若干装入体积为 j 的箱子时，所能使用的最大体积。

我们的目标是：
找出 dp[n][vs]，即使用了全部物品后，在体积为 vs 的箱子中能装下的最大体积，用 vs - dp[n][vs] 得到最小剩余空间。

三、状态转移方程

对于任意一个物品 i：

  • 如果不放第 i 个物品，则 dp[i][j] = dp[i-1][j]
    • (因为不放，所以dp[i][j] 就是 前 i-1 个物品中选择若干装入体积为 j 的箱子时，所能使用的最大体积)
  • 如果放第 i 个物品，则必须满足 j >= v[i]，此时 dp[i][j] = max(dp[i-1][j-v[i]] + v[i], dp[i-1][j])
    • (当保证当前体积 能够容纳v[i]体积的前提下 dp[i][j]就要在放与不放两种情况下 产生的解中取更大的)

所以状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + v[i]) 当 j >= v[i]
dp[i][j] = dp[i-1][j] 当 j < v[i]

四、初始化条件

没有物品时不能占用任何空间，因此：

前 0 个物品中选择若干装入体积为 j 的箱子时，所能使用的最大体积为0

//dp[0][n]=0;
//这里在定义dp数组时，已经隐式初始化过了

其他位置初始值默认为0即可。

五、具体实现步骤详解

1. 输入处理部分

ll vs, n;
cin >> vs >> n;vector<ll> v(n + 1, 0);
for (ll i = 1; i <= n; i++) {cin >> v[i];
}
  • 使用数组 v[i] 存储每个物品的体积；
  • 注意这里的有效数据从下标（1,1）开始存储

2. 动态规划计算部分

vector<vector<ll>> dp(n + 1, vector<ll>(vs + 1, 0));// 初始化for (ll i = 1; i <= n; i++) {for (ll j = 1; j <= vs; j++) {if (j >= v[i]) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i]);} else {dp[i][j] = dp[i - 1][j];}}
}
  • 初始化第0层；
  • 然后逐层向下计算每一位置的最大使用体积；
  • 每次选择是否放置当前物品，更新最大使用体积。

3. 输出结果

ll ender = dp[n][vs];
cout << vs - ender << endl;
  • 结果就是：
    找到 使用了全部物品后，在体积为 vs 的箱子中能装下的最大体积 即dp[n][vs]，用 vs - dp[n][vs] 得到最小剩余空间。

六、完整代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main()
{//1.输入处理部分// 定义变量 vs（箱子总容量）和 n（物品数量）ll vs, n;cin >> vs >> n;// 创建体积数组 v，下标从 1 开始，v[i] 表示第 i 个物品的体积vector<ll> v(n + 1, 0);// 输入每个物品的体积for (ll i = 1; i <= n; i++){cin >> v[i];}//2. 动态规划计算部分// 定义动态规划数组 dp[i][j]// dp[i][j]：从前 i 个物品中选择若干个，使得它们的总体积为不超过 j 的最大使用空间// 初始值全为 0vector<vector<ll>> dp(n + 1, vector<ll>(vs + 1, 0));// 动态规划过程开始，i 从 1 到 n，表示处理前 i 个物品for (ll i = 1; i <= n; i++){// j 表示当前箱子的容量，从 1 到 vsfor (ll j = 1; j <= vs; j++){// 当前物品体积小于等于当前容量，可以选择放或者不放if (j >= v[i]){// 放的情况：dp[i - 1][j - v[i]] + v[i]（前 i-1 个物品在 j-v[i] 容量下的最大使用空间 + 当前物品体积）// 不放的情况：dp[i - 1][j]（前 i-1 个物品在容量 j 下的最大使用空间）dp[i][j] = max(dp[i - 1][j - v[i]] + v[i], dp[i - 1][j]);}else{// 当前物品体积大于当前容量，不能放，只能继承上一层的结果dp[i][j] = dp[i - 1][j];}}}// 找到 使用了全部物品后，在体积为 vs 的箱子中能装下的最大体积 即dp[n][vs]//用 vs - dp[n][vs] 得到最小剩余空间。ll ender = dp[n][vs];// 最小剩余空间 = 总容量 - 最大使用空间cout << vs - ender << endl;return 0;
}

七、以样例输入为例手动模拟

输入：

24
6
8
3
12
7
9
7

在这里插入图片描述

最终结果为24-24==0

八、时间 & 空间复杂度分析

  • 时间复杂度： O(n×vs)，因为两重循环，每层最多处理 vs 个元素。
  • 空间复杂度： O(n×vs)，使用了一个二维数组存储路径和。

总结

步骤内容
状态定义dp[i][j] 表示从前 i 个物品中选择若干装入体积为 j 的箱子时，所能使用的最大体积
状态转移dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + v[i]) 当 j >= v[i]
dp[i][j] = dp[i-1][j] 当 j < v[i]
初始条件第0层根据第0个物品体积初始化
最终答案vs - dp[n][vs]
时间复杂度O(n×vs)
空间复杂度O(n×vs)

题解：滚动数组优化版（一维数组）

一、状态定义（一维）

设 dp[j] 表示当前处理到某个物品时，在容量为 j 的箱子中能装下的最大体积。

注意：这个状态是通过不断更新一个一维数组实现的，而不是二维数组。

二、状态转移方程（滚动数组）

对于第 i 个物品：

  • 如果不放它，则 dp[j] 不变（继续使用上层的结果）；
  • 如果放它，则必须满足 j >= v[i]，此时新的值为 max(dp[j], dp[j - v[i]] + v[i])

因此状态转移方程为：

if j >= v[i]:dp[j] = max(dp[j], dp[j - v[i]] + v[i])

关键点：内层循环要从后往前遍历容量 j，这样可以确保每个物品只被选一次。

三、初始条件

  • dp[0] = 0，表示容量为 0 时无法装任何物品。
  • 其余位置初始化为 0，表示初始状态下未装入任何物品。

四、实现细节详解

1. 输入处理部分

ll vs, n;
cin >> vs >> n;vector<ll>v(n + 1, 0);for (ll i = 1; i <= n; i++)
{cin >> v[i]; 
}
  • 使用 v[i] 存储第 i 个物品的体积，索引从1开始；
  • 读取输入数据。

2. 初始化动态规划数组（滚动数组）

vector<ll> dp(vs + 1, 0);
  • 创建一个大小为 vs + 1 的一维数组；
  • 所有元素初始化为 0，表示没有物品时无法占用空间。

3. 动态规划计算部分（滚动数组）

for (ll i = 1; i <= n; i++) // 遍历每个物品
{for (ll j = vs; j >= v[i]; j--) // 从后往前遍历容量{dp[j] = max(dp[j], dp[j - v[i]] + v[i]);}
}

4.⚠️ 注意点（关键！）

项目说明
内层循环方向必须 从后往前 遍历容量 j，否则会重复选取同一个物品
原因在一维数组中，如果从前向后更新，上一层产生的结果会影响后面的状态，导致物品被多次选择
正确做法从大到小更新容量 j，确保每次更新都基于上一轮的状态
4.1.为什么从前往后遍历容量j会重复选取同一个物品呢
  • 以样例输入为例手动模拟：

输入：

24
6
8
3
12
7
9
7

如果从前往后遍历容量j结果是这样的：
在这里插入图片描述

4.2.当然从后往前遍历可以从vs遍历到1,也可以从vs遍历到v[i]

当你从后向前遍历容量时，既可以遍历到 1 也可以只遍历到 v[i]。两者都能保证算法的正确性，但它们在效率和逻辑上有一些细微的区别。下面是详细的整理和原因分析：

从后向前遍历容量

无论选择遍历到 1 还是 v[i]，关键在于确保每个物品仅被选择一次。通过从后向前遍历容量，我们避免了同一个物品被多次选择的问题。

遍历到 1

  • 实现方式：

    for (ll j = vs; j >= 1; j--)
{if (j >= v[i]){dp[j] = max(dp[j], dp[j - v[i]] + v[i]);}
}

  • 优点：

    • 更加直观，循环结构更简单。
    • 不需要额外判断是否 j >= v[i]，因为这个条件已经在循环内部处理了。

  • 缺点：

    • 对于那些小于当前物品体积 v[i] 的容量（即 j < v[i]），这些状态不会发生变化，因此对这些容量进行更新是不必要的，增加了计算开销。
遍历到 v[i]

  • 实现方式：

    for (ll j = vs; j >= v[i]; j--)
{dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
}

  • 优点：

    • 只对那些可以放下当前物品的容量进行更新，减少了不必要的计算。
    • 提高了效率，尤其是在物品体积较大时效果更加明显。

  • 缺点：

    • 循环边界稍微复杂一点，但这种复杂性是可以接受的，并且提高了效率。
小结
方式描述优点缺点
遍历到 1从 vs 到 1，在循环内部检查 j >= v[i]实现简单，逻辑清晰对于 j < v[i] 的容量进行了不必要的更新，效率较低
遍历到 v[i]从 vs 到 v[i]，直接跳过不能放下的容量减少了不必要的计算，提高效率边界条件稍微复杂一些

5. 输出结果

ll ender = dp[vs];
cout << vs - ender;
  • dp[vs] 表示在不超过箱子容量 vs 的前提下，能装下的最大体积；
  • 最小剩余空间就是 vs - dp[vs]。

时间 & 空间复杂度分析

类型复杂度说明
时间复杂度O(n × vs)两重循环，每层最多处理 vs 个容量
空间复杂度O(vs)使用了一维数组代替二维数组，大大节省了内存

完整代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main()
{// vs 表示箱子的总体积// n 表示物品的数量ll vs, n;cin >> vs >> n;// v[i] 表示第 i 个物品的体积// 使用索引从 1 开始，方便和动态规划下标对应vector<ll> v(n + 1, 0);// 读取每个物品的体积for (ll i = 1; i <= n; i++){cin >> v[i];}// 动态规划数组 dp[j]// dp[j]: 在容量为 j 的情况下，能装入物品的最大体积// 使用一维数组代替二维数组，进行空间优化（滚动数组）vector<ll> dp(vs + 1, 0);// 动态规划主循环for (ll i = 1; i <= n; i++) // 遍历每一个物品{// 内层循环必须从后往前遍历容量 j// 原因：防止当前物品被重复选择（保证是 0-1 背包）// j >= v[i]：因为当容量小于当前物品体积时，无法放入该物品，无需更新// 可以写成：// for (ll j = vs; j >= 1; j--)//     if (j >= v[i]) ...// 但更高效的做法是从 vs 遍历到 v[i]，跳过无效状态，提升效率for (ll j = vs; j >= v[i]; j--){// 状态转移方程：// 不选当前物品：dp[j] 保持不变// 选当前物品：dp[j - v[i]] + v[i]// 取两者的最大值作为新的 dp[j]dp[j] = max(dp[j], dp[j - v[i]] + v[i]);}}// 最终答案：// dp[vs] 表示在不超过总容量 vs 的前提下，可以装入的最大体积// 最小剩余空间 = 总容量 - 最大使用空间cout << vs - dp[vs] << endl;return 0;
}

总结

步骤内容
状态定义dp[j] 表示容量为 j 时能装下的最大体积
状态转移dp[j] = max(dp[j], dp[j - v[i]] + v[i])
初始条件dp[j] = 0，所有容量初始为空
滚动数组优化使用一维数组，内层循环从后往前
最终答案vs - dp[vs]
时间复杂度O(n × vs)
空间复杂度O(vs)

从二维改成滚动数组的技巧：

二维dp代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main()
{//1.输入处理部分// 定义变量 vs（箱子总容量）和 n（物品数量）ll vs, n;cin >> vs >> n;// 创建体积数组 v，下标从 1 开始，v[i] 表示第 i 个物品的体积vector<ll> v(n + 1, 0);// 输入每个物品的体积for (ll i = 1; i <= n; i++){cin >> v[i];}//2. 动态规划计算部分// 定义动态规划数组 dp[i][j]// dp[i][j]：从前 i 个物品中选择若干个，使得它们的总体积为不超过 j 的最大使用空间// 初始值全为 0vector<vector<ll>> dp(n + 1, vector<ll>(vs + 1, 0));// 动态规划过程开始，i 从 1 到 n，表示处理前 i 个物品for (ll i = 1; i <= n; i++){// j 表示当前箱子的容量，从 1 到 vsfor (ll j = 1; j <= vs; j++){// 当前物品体积小于等于当前容量，可以选择放或者不放if (j >= v[i]){// 放的情况：dp[i - 1][j - v[i]] + v[i]（前 i-1 个物品在 j-v[i] 容量下的最大使用空间 + 当前物品体积）// 不放的情况：dp[i - 1][j]（前 i-1 个物品在容量 j 下的最大使用空间）dp[i][j] = max(dp[i - 1][j - v[i]] + v[i], dp[i - 1][j]);}else{// 当前物品体积大于当前容量，不能放，只能继承上一层的结果dp[i][j] = dp[i - 1][j];}}}// 找到 使用了全部物品后，在体积为 vs 的箱子中能装下的最大体积 即dp[n][vs]//用 vs - dp[n][vs] 得到最小剩余空间。ll ender = dp[n][vs];// 最小剩余空间 = 总容量 - 最大使用空间cout << vs - ender << endl;return 0;
}

第一步：先直接删掉二维中的一维

得到代码：

#include<iostream>
#include<vector>
using namespace std;
using ll = long long;int main()
{//1.输入处理部分// 定义变量 vs（箱子总容量）和 n（物品数量）ll vs, n;cin >> vs >> n;// 创建体积数组 v，下标从 1 开始，v[i] 表示第 i 个物品的体积vector<ll> v(n + 1, 0);// 输入每个物品的体积for (ll i = 1; i <= n; i++){cin >> v[i];}//2. 动态规划计算部分// 定义动态规划数组 dp[j]// dp[j]：从前 i 个物品中选择若干个，使得它们的总体积为不超过 j 的最大使用空间// 初始值全为 0vector<ll>dp(vs + 1, 0);// 动态规划过程开始，i 从 1 到 n，表示处理前 i 个物品for (ll i = 1; i <= n; i++){// j 表示当前箱子的容量，从 1 到 vsfor (ll j = 1; j <= vs; j++){// 当前物品体积小于等于当前容量，可以选择放或者不放if (j >= v[i]){// 放的情况：dp[j - v[i]] + v[i]（前 i-1 个物品在 j-v[i] 容量下的最大使用空间 + 当前物品体积）// 不放的情况：dp[j]（前 i-1[等价于上一层的结果] 个物品在容量 j 下的最大使用空间）dp[j] = max(dp[j - v[i]] + v[i], dp[j]);}else{// 当前物品体积大于当前容量，不能放，只能继承上一层的结果dp[j] = dp[j];}}}// 找到 使用了全部物品后，在体积为 vs 的箱子中能装下的最大体积 即dp[vs]//用 vs - dp[vs] 得到最小剩余空间。ll ender = dp[vs];// 最小剩余空间 = 总容量 - 最大使用空间cout << vs - ender << endl;return 0;
}

但是这里会有重复选取的问题 以及 冗余代码的问题

第三步：更改内层循环的遍历顺序（解决重复选取问题）

删除冗余代码（得到滚动数组的优化版本）

#include<iostream>
#include<vector>
using namespace std;
using ll = long long;int main()
{//1.输入处理部分// 定义变量 vs（箱子总容量）和 n（物品数量）ll vs, n;cin >> vs >> n;// 创建体积数组 v，下标从 1 开始，v[i] 表示第 i 个物品的体积vector<ll> v(n + 1, 0);// 输入每个物品的体积for (ll i = 1; i <= n; i++){cin >> v[i];}//2. 动态规划计算部分// 定义动态规划数组 dp[j]// dp[j]：从前 i 个物品中选择若干个，使得它们的总体积为不超过 j 的最大使用空间// 初始值全为 0vector<ll>dp(vs + 1, 0);// 动态规划过程开始，i 从 1 到 n，表示处理前 i 个物品for (ll i = 1; i <= n; i++){// j 表示当前箱子的容量，从 1 到 vs（注意倒序遍历，防止重复选取问题）//可以进一步优化为：/*for (ll j = vs; j >= v[i]; j--){dp[j] = max(dp[j - v[i]] + v[i], dp[j]);}*/for (ll j = vs; j >= 1; j--){//去掉冗余代码：这里以注释表示，更直观// 当前物品体积小于等于当前容量，可以选择放或者不放if (j >= v[i]){// 放的情况：dp[j - v[i]] + v[i]（前 i-1 个物品在 j-v[i] 容量下的最大使用空间 + 当前物品体积）// 不放的情况：dp[j]（前 i-1[等价于上一层的结果] 个物品在容量 j 下的最大使用空间）dp[j] = max(dp[j - v[i]] + v[i], dp[j]);}//else//{//    // 当前物品体积大于当前容量，不能放，只能继承上一层的结果//    dp[j] = dp[j];//}}}// 找到 使用了全部物品后，在体积为 vs 的箱子中能装下的最大体积 即dp[vs]//用 vs - dp[vs] 得到最小剩余空间。ll ender = dp[vs];// 最小剩余空间 = 总容量 - 最大使用空间cout << vs - ender << endl;return 0;
}

最后若想再优化一点的话，可以从vs倒序遍历到v[i]

#include<iostream>
#include<vector>
using namespace std;
using ll = long long;int main()
{//1.输入处理部分// 定义变量 vs（箱子总容量）和 n（物品数量）ll vs, n;cin >> vs >> n;// 创建体积数组 v，下标从 1 开始，v[i] 表示第 i 个物品的体积vector<ll> v(n + 1, 0);// 输入每个物品的体积for (ll i = 1; i <= n; i++){cin >> v[i];}//2. 动态规划计算部分// 定义动态规划数组 dp[j]// dp[j]：从前 i 个物品中选择若干个，使得它们的总体积为不超过 j 的最大使用空间// 初始值全为 0vector<ll>dp(vs + 1, 0);// 动态规划过程开始，i 从 1 到 n，表示处理前 i 个物品for (ll i = 1; i <= n; i++){// j 表示当前箱子的容量，从 1 到 vs（注意倒序遍历，防止重复选取问题）//可以进一步优化为：for (ll j = vs; j >= v[i]; j--){dp[j] = max(dp[j - v[i]] + v[i], dp[j]);}//for (ll j = vs; j >= 1; j--)//{//    //去掉冗余代码：这里以注释表示，更直观//    //    // 当前物品体积小于等于当前容量，可以选择放或者不放//    if (j >= v[i])//    {//        // 放的情况：dp[j - v[i]] + v[i]（前 i-1 个物品在 j-v[i] 容量下的最大使用空间 + 当前物品体积）//        // 不放的情况：dp[j]（前 i-1[等价于上一层的结果] 个物品在容量 j 下的最大使用空间）//        dp[j] = max(dp[j - v[i]] + v[i], dp[j]);//    }//    //else//    //{//    //    // 当前物品体积大于当前容量，不能放，只能继承上一层的结果//    //    dp[j] = dp[j];//    //}//}}// 找到 使用了全部物品后，在体积为 vs 的箱子中能装下的最大体积 即dp[vs]//用 vs - dp[vs] 得到最小剩余空间。ll ender = dp[vs];// 最小剩余空间 = 总容量 - 最大使用空间cout << vs - ender << endl;return 0;
}
http://www.xdnf.cn/news/4129.html

相关文章：

  • Sublime PrettyJson 快捷键
  • 在 Laravel 12 中实现 WebSocket 通信时进行身份验证
  • ts bug 找不到模块或相应类型的声明，@符有红色波浪线
  • Prometheus实战教程：k8s平台-使用文件服务发现案例
  • Android Retrofit框架分析(三)：自动切换回主线程；bulid的过程；create方法+ServiceMethod源码了解
  • 【Azure Redis 缓存】关于Azure Cache for Redis 服务在传输和存储键值对(Key/Value)的加密问题
  • Windows系统修改Docker Desktop(WSL2)内存分配
  • Facebook隐私保护措施的优缺点解析
  • Java面试全栈解析：Spring Boot、Kafka与Redis实战揭秘
  • Jenkins+Newman实现接口自动化测试
  • 蓝桥杯-通电(最小生成树java)
  • Axure ： 列表分页、 列表翻页
  • 第1.3讲、什么是 Attention？——从点菜说起 [特殊字符]️
  • FastJSON 使用 `Feature.OrderedField` 修复 `JSONObject` 序列化字段顺序问题
  • 用 GRPO 魔法点亮Text2SQL 的推理之路：让模型“思考”得更像人类
  • AI服务器的作用都有哪些?
  • 【工具使用-数据可视化工具】Apache Superset
  • Cursor 被封解决方案
  • 2、Kafka Replica机制与ISR、HW、LEO、AR、OSR详解
  • .NET 通过回调函数执行 Shellcode启动进程
  • 广州华锐视点邀您参与2025广交会VRAR展【5月10-12日】
  • 快速体验 .NET9 提供的 HybridCache 混合缓存
  • wrod生成pdf。[特殊字符]改背景
  • 基于Piecewise Jerk Speed Optimizer的速度规划算法(附ROS C++/Python仿真)
  • C++多态详解
  • ORCAD打印pdf
  • Docker手动重构Nginx镜像，融入Lua、Redis功能
  • 【C++】WSL常用语法
  • 先滤波再降采样 还是 先降采样再滤波
  • IL2CPP 技术深度解析