首页>>科技 > >>正文

01背包问题是什么?01背包问题的动态规划解法怎么写?

2026-11-19 11:18:05 来源:AI

01背包问题:算法入门绕不开的经典考题,解法拆解看这篇

在互联网大厂算法面试、计算机专业考研笔试中,动态规划相关问题一直是高频考点,而01背包问题更是动态规划体系里的“入门敲门砖”——不仅能帮你理解动态规划的核心逻辑,还能延伸出无数变种题型。今天就把这个问题的本质和解法彻底讲透。

01背包问题是什么?01背包问题的动态规划解法怎么写?

01背包问题:一个“二选一”的经典场景

很多人第一次接触01背包问题时,会被名字搞懵,其实它的本质是一个非常贴近生活的“选择难题”:假设你有一个容量固定的背包,面前有n件物品,每件物品都有固定的重量和价值,且每件物品只能选一次(要么装要么不装),请问你怎么选,才能让背包里的物品总价值最大?

这里的“01”就是核心约束:0代表不选这件物品,1代表选这件物品,没有“选一半”的可能。比如背包容量10,有3件物品:重量2价值3、重量3价值4、重量5价值6,你需要在不超重的前提下,让总价值最高。

动态规划解法:拆解问题的核心逻辑

动态规划解决01背包的关键,是把复杂的大问题拆解成重叠的子问题,再记录子问题的最优解来避免重复计算。具体步骤可以分成3步: 首先,定义状态。我们用`dp[i][j]`表示“前i件物品,背包容量为j时能获得的最大价值”,这个状态定义是整个解法的核心。 其次,推导状态转移方程。对第i件物品,我们有两种选择:如果不选它,那么`dp[i][j] = dp[i-1][j]`(前i件的最大价值等于前i-1件的最大价值);如果选它,前提是重量不超过当前容量j,此时`dp[i][j] = dp[i-1][j-重量i] + 价值i`(前i-1件在容量j-重量i时的最大价值,加上第i件的价值)。最终取两种选择的最大值,即`dp[i][j] = max(不选的情况, 选的情况)`。 最后,确定边界条件。当没有物品(i=0)或背包容量为0(j=0)时,最大价值都是0。

空间优化:从二维数组到一维数组

基础的二维数组解法虽然逻辑清晰,但空间复杂度是O(n*W)(n是物品数,W是背包容量),我们可以优化成一维数组:用`dp[j]`表示容量为j时的最大价值,此时状态转移方程简化为`dp[j] = max(dp[j], dp[j-重量i] + 价值i)`。需要注意的是,遍历容量时必须从大到小,避免重复计算同一物品。

相关问题及解答

1. 问:01背包问题为什么叫“01”背包? 答:因为每件物品只有两种选择状态:0(不选)或1(选),不存在部分选择的情况,因此得名。

2. 问:动态规划解法的核心优势是什么? 答:动态规划通过记录子问题的最优解,避免了暴力枚举的重复计算,时间复杂度从暴力的O(2ⁿ)降低到O(n*W),大幅提升了计算效率。

3. 问:01背包问题的动态规划解法能应用在实际场景中吗? 答:可以,比如项目选择(每个项目只能选一次,有成本和收益,求最大收益)、预算分配(预算固定,每个方案只能选一次,求最优分配)等场景,都可以用01背包的动态规划解法解决。

标签: 01背包问题是什么01背包问题的动态规划

最近更新

更多》

要闻

更多》