Lazy loaded image
笔记
习题8.2
Words 3960Read Time≈ 10 min
2026-3-3
2026-3-3
type
Post
status
Published
date
Mar 3, 2026
slug
summary
tags
算法笔记
category
笔记
icon
password
  1. 背包问题使用动态规划求解
      2. a. 对于下列背包问题的实列，应用自底向上动态规划算法求解。称重量W=6
      物品
      重量
      价值/美元
      1
      3
      25
      2
      2
      20
      3
      1
      15
      4
      4
      40
      5
      5
      50
      对于给定的背包问题实例（背包承重 W=6，物品数量为5，各物品重量和价值如上表），采用自底向上的动态规划算法求解。具体过程如下：
      表格法
      1. 动态规划递推式
      定义 dp[i][w]表示考虑前 i个物品、背包容量为 w时能获得的最大价值。状态转移方程为：
      • 若w < weight[i]，则dp[i][w]=dp[i-1][w] (当前物品太重，背包放不下)
      • 否则，max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) （在不放和放入当前物品中选择最大值）。
      初始条件：dp[0][w] = 0（0个物品时价值为0）
      2. 填表
      ㅤ
      0
      1
      2
      3
      4
      5
      6
      0
      0
      0
      0
      0
      0
      0
      0
      1
      0
      0
      0
      25
      25
      25
      25
      2
      0
      0
      20
      25
      25
      45
      45
      3
      0
      15
      20
      35
      40
      45
      60
      4
      0
      15
      20
      35
      40
      55
      60
      5
      0
      15
      20
      35
      40
      55
      65
      集合法
      1. 列出所有可能集合
        1. {}
        2. {A}、{B}、{C}、{D}、{E}
        3. {A,B}、{A,C}、{A,D}、{A,E}
        4. {A,B,C}、{A,B,D}、{A,B,E}
        5. {A,C,D}、{A,C,E}
        6. {A,D,E}
        7. ………
      1. 确定最大价值
          2. 从可行子集中找出最大价值：
          • 最大价值为 65，对应子集 {3,5}。
      1. 检查是否有其他子集达到相同价值
          2. 检查所有可行子集，价值为65的只有 {3,5}。因此，最优子集唯一。
      b. a中的实例中有多少个不同的最优子集？
      不同的最优子集数量为1
      如何求得最优子集？
      1. 使用回溯法求解所选物品
        1. 从dp[5][6] 开始回溯：
            • dp[5][6]≠dp[4][6] 说明5号物品被选中。选中后剩余容量：6-5=1，查看dp[4][1]。(dp[4][1]来自 dp[3][1])
            • dp[4][1]=dp[3][1] 物品4重量4大于背包剩余容量1，所以物品4没被选中。继续查看dp[3][1] 。
            • dp[3][1] = 15≠ dp[2][1] = 0，说明物品3被选中。选中后剩余容量: 1-1=0，结束。
        2. 因此，所选物品为：物品3（重量1，价值15）和物品5（重量5，价值50），总重量恰好为6，总价值65。
      1. 排除其他可能性
      • 其他潜在组合（如物品2+物品4）总价值仅为60美元，无法通过添加物品5提升至65美元。
      • 动态规划表中所有路径均指向唯一解，无其他子集能达到同等最优值。
      c. 一般来说，如何从动态规划算法所生成的表中判断出背包问题的实例是不是具有不止一个最优子集?
      要判断背包问题实例是否具有多个最优子集，可以通过分析动态规划表在回溯过程中是否存在分支来实现。具体步骤如下：
      1. 填充动态规划表：按照标准0/1背包问题的动态规划方法，计算并填充分子问题最优值的表格 dp[i][w]，其中 i=0,…,n，w=0,…,W。
      1. 从最终状态回溯：从最终状态 (n,W)开始，逆向检查每个状态 (i,w)的来源。对于每个 i>0：
          • 如果 dp[i][w]=dp[i−1][w]，则不选物品 i是一种可能的选择。
          • 如果 w≥weight[i]且 dp[i][w]=dp[i−1][w−weight[i]]+value[i]，则选物品 i是另一种可能的选择。
      1. 检查分支：如果在回溯过程中，任何状态 (i,w)同时满足上述两个条件（即两种选择都达到相同的最优值），则存在分支，表明至少有两个不同的最优子集（因为从该状态出发，不选和选物品 i会导向不同的物品组合）。
      1. 结论：如果回溯全程未遇到任何分支，则最优子集唯一；否则，存在多个最优子集。
      这种方法利用了动态规划表的递推关系，通过检查状态转移中的“平局”来识别多个最优解的存在性，无需枚举所有子集。
  1. 伪代码
      2. a. 为背包问题写一段自底向上的动态规划算法的伪代码
      b. 写一段伪代码，使得可以从背包问题的自底向上动态规划算法生成的表中求得最优子集的组成。
  1. 对于背包问题的自底向上动态规划算法，请证明:
      2. a. 它的时间效率属于Θ(nW)b.它的空间效率属于Θ(nw)。
      notion image
      c. 从一张填好的动态规划表中求得最优子集的组合所用的时间属于O(n)。
      从填好的动态规划表中回溯求解最优子集组合的过程，通常是从最终状态 dp[n][W]开始，逆序检查每个物品是否被选中。
      对于每个物品 i（从 n到 1），只需常数时间的比较（如判断 dp[i][w]是否等于 dp[i−1][w]或是否等于 dp[i−1][w−weight[i]]+value[i]），并更新剩余容量 w。该过程最多循环 n次，因此时间复杂度为 O(n)。所以，题中说法正确。
  1. 判断正误
      2. a.背包问题实例的动态规划表中某一行值的序列总是非递减的，
      正确 ✅
      理由：动态规划表的第 i行表示在考虑前 i个物品时，背包容量从 0到 W对应的最大价值。由于物品价值非负，当背包容量 w增加时，可容纳的物品不会减少（至少可以保持原有选择），最大价值不会降低，因此该行序列非递减。
      数学表述：
      • 对于固定的 i，若 <，则有 dp[i][]≤dp[i][]。
      b.背包问题实例的动态规划表中某一列值的序列总是非递减的。
      正确 ✅
      理由：动态规划表的第 w列表示在背包容量固定为 w时，考虑前 1到 n个物品对应的最大价值。随着可考虑的物品数量 i增加，可供选择的物品增多（或至少保持不变），因此最大价值不会降低，该列序列非递减。
      数学表述：
      • 对于固定的 w，若 ，则有 dp[][w]≤dp[][w]。
  1. 假设n种物品中每种物品的数量不限，为该背包问题设计一个动态规划算法并分析该算法的时间效率。
      2. 二维DP算法设计
      1. 状态定义
      • 设 dp[i][c]表示考虑前 i种物品（物品种类从1到i），在背包容量为 c时能获得的最大价值。
      2. 状态转移方程
      • 对于第 i种物品（重量为 w_i，价值为 v_i），我们可以选择放入0个、1个或多个：
          • notion image
      更高效的递推式（避免枚举k）：
      notion image
      关键：当 ≤ c时，dp[i][c - ] + 中用的是 dp[i][c - ]而不是 dp[i-1][c - ]，这表示我们可以在考虑前i种物品的基础上继续放入第i种物品。
      3. 算法实现
      时间效率分析
      时间复杂度：
      • 需要填充一个 (n+1) × (W+1)的二维表
      • 每个单元格的计算是常数时间 O(1)
      • 总时间复杂度：O(nW)
      空间复杂度：
      • 二维DP表需要 (n+1) × (W+1)的存储空间
      总空间复杂度：O(nW)
      与一维DP的对比
      维度
      状态定义
      时间复杂度
      空间复杂度
      特点
      二维DP
      dp[i][c]
      O(nW)
      O(nW)
      直观，易于理解，可回溯
      一维DP
      dp[c]
      O(nW)
      O(W)
      空间优化，更高效
      回溯求解具体方案
  1. 对第1题中给出的背包问题的实例应用记忆功能方法。在动态规划表中找出这样
的单元格:
1.在这个实例中，从来没有被记忆功能方法计算过的单元格
ㅤ
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
0
0
25
25
25
25
2
0
0
20
-1
-1
45
45
3
0
15
20
-1
-1
-1
60
4
0
15
-1
-1
-1
-1
60
5
0
15
-1
-1
-1
-1
65
2.不需要重新计算就能使用的单元格。
ㅤ
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
0
0
25
25
25
25
2
0
0
20
-1
-1
45
45
3
0
15
20
-1
-1
-1
60
4
0
15
-1
-1
-1
-1
60
5
0
15
-1
-1
-1
-1
65
3.回忆记忆功能伪代码
  1. 证明背包问题的记忆功能算法的时间效率类型和自底向上算法是相同的(参见第3题)。
      2. 证明：
      notion image
      📌
      关于“递归栈很大”的疑问：
      递归深度可能达到 O(n)或 O(W)，这可能导致栈空间的过度消耗（甚至栈溢出），但栈深度并不改变时间复杂度的渐近阶。
      时间复杂度关注的是基本操作次数，递归调用本身在理论模型中视为常数时间操作。因此，即使递归栈很大，记忆功能算法的时间复杂度类型依然与自底向上算法相同，均为 Θ(nW)。不过在实际应用中，递归栈过大会带来实现上的限制，此时自底向上方法更为稳健。
  1. 为什么根据公式 计算二项式系数时，记忆功能法不是一个好方法?
      2. 主要有以下几点原因：
      1. 递归深度与函数调用开销
      • 问题：计算 C(n,k)需要递归计算 C(n−1,k−1)和 C(n−1,k)，递归深度可能达到 O(n)。
      • 影响：深递归会导致大量函数调用开销（如栈帧分配、参数传递），即使有缓存，递归调用本身的成本仍较高。
      • 对比：自底向上的动态规划（直接填充二维表格）完全避免递归，效率更高。
      2. 计算顺序的局限性
      • 记忆化法的顺序：递归调用顺序由问题依赖关系决定，可能导致缓存未命中或非顺序内存访问。
      • 自底向上的优势：直接从基础情况 C(i,0)=1和 C(i,i)=1开始，按行（或列）顺序填充表格，内存访问连续，更符合计算机缓存友好性。
      3. 状态覆盖不完整
      • 记忆化法的特点：只计算递归过程中实际访问的子问题。
      • 潜在问题：若需要多次计算不同 (n,k)的组合数，记忆化法可能需重复初始化缓存；而自底向上法一次计算即可生成完整的帕斯卡三角形（即整个组合数表），后续查询任意 C(n,k)均为 O(1)时间。
      4. 对称性未充分利用
      • 组合数性质：C(n,k)=C(n,n−k)。
      • 记忆化法的局限：递归过程中可能分别计算 C(n,k)和 C(n,n−k)，导致重复缓存（除非显式优化）。
      • 自底向上法：可仅计算三角形上半部分，直接利用对称性减少一半计算量。
      5. 边界条件处理复杂
      • 递归的边界：需显式处理 k=0、k=n、k>n等情况，每次递归都需判断。
      • 迭代法：边界条件在初始化时一次性处理，后续循环中无需判断。
      6. 时间复杂度对比
      • 两种方法的时间复杂度均为 O(nk)：但记忆化法的常数因子更大（递归调用、缓存查找开销）。
      • 空间复杂度：两者均为 O(nk)，但自底向上法可用滚动数组优化至 O(k)，记忆化法较难实现此优化。
      总结
      虽然记忆功能法能避免重复计算，但针对二项式系数的计算：
      • 自底向上动态规划（直接填充表格）更简单、高效，且易于优化（如利用对称性、滚动数组）。
      • 记忆功能法更适合子问题依赖复杂、不规则，或仅需计算少数状态的问题；而二项式系数的计算具有规则的结构，更适合迭代法。
      因此，在计算二项式系数时，通常推荐使用自底向上的动态规划而非记忆功能法。
 
上一篇
动态规划3-用记忆化技术解决背包问题
下一篇
从 Heo 到 Heo Pro