0-1 背包问题
640 字
3 分钟
0-1 背包问题
题意概要：有 n 个物品和一个容量为 W 的背包，每个物品有重量 w_{i} 和价值 v_{i} 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的 和 ，这类问题便被称为「0-1 背包问题」。
例题中已知条件有第 i 个物品的重量 w_{i}，价值 v_{i}，以及背包的总容量 W。 设 DP 状态 f_{i,j} 为在只能放前 i 个物品的情况下，容量为 j 的背包所能达到的最大总价值。
考虑转移。假设当前已经处理好了前 i-1 个物品的所有状态，那么对于第 i 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 f_{i-1,j}；当其放入背包时，背包的剩余容量会减小 w_{i}，背包中物品的总价值会增大 v_{i}，故这种情况的最大价值为 f_{i-1,j-w_{i}}+v_{i}。 由此可以得出状态转移方程：
物品放入背包后，总重量增加 ，背包剩余容量减少，所以容量是
1. 二维动态规划解法
最直接的思路是使用二维数组来记录状态。定义dp[i][j]表示前i个物品在背包容量为j时所能达到的最大价值。
状态转移方程：
- 如果不选第
i个物品，dp[i][j] = dp[i-1][j]。 - 如果选第
i个物品，dp[i][j] = dp[i-1][j-wi] + vi，其中wi是第i个物品的重量，vi是其价值。
综合以上两种情况：
dp[i][j]=max(dp[i−1][j],dp[i−1][j−wi]+vi)时间复杂度：O(n * W)，空间复杂度也是O(n * W)。
2. 一维动态规划优化
通过观察上述二维动态规划方程，可以发现dp[i][j]只依赖于dp[i-1][j]和dp[i-1][j-wi]。因此，dp数组当前行的值只与前一行有关，所以我们可以通过一维数组来保存这些状态，从而降低空间复杂度。
优化思路：
- 使用一维数组
dp[j]，表示在背包容量为j时，能得到的最大价值。 - 按照从大到小的顺序更新
dp[j]，这样可以确保在计算dp[j]时，dp[j-wi]使用的是上一轮的值，即“前一行”的状态。
状态转移方程（与二维数组时类似）
dp[j]=max(dp[j],dp[j−wi]+vi)文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
Grafana 可视化与监控
云原生与运维Grafana 的定位、常见数据源与 Grafana + Prometheus 经典监控链路。
2
微服务之间如何传递 trace
后端开发跨服务传递的是 trace 上下文而非 tracer：HTTP header、gRPC metadata 与 MQ 消息头的标准做法。
3
kubectl port-forward 端口转发
云原生与运维kubectl port-forward 转发 Pod/Service、让局域网访问以及常用排查命令。
4
Wooden Toy Festival 题解：二分答案与贪心验证
数据结构与算法三个雕刻师制作 n 个玩具的最小等待时间：二分答案 + 排序后贪心分配验证，附完整 C++ 代码。
5
kubectl 常用命令速查
云原生与运维kubectl 查看集群/资源/日志、进入容器、本地访问服务与部署删除的常用命令。
随机文章随机推荐