EP11. “Knapsack Problem 背包问题”

首页 › Microsoft 工具 › Excel · VBA · Loop · EP11

约 8 分钟· #EP11#Excel#Loop

🔒 登录后可标记已读

背包问题是经典的最优化问题：给一组各有重量和价值的物品，在总重量不超过限制的前提下，找出总价值最大的物品组合
这篇用 5 层嵌套循环暴力穷举所有 2⁵ = 32 种「选或不选」的组合来求解
前置知识：多层嵌套循环和 If Then 判断
学完能理解「暴力穷举法」这种最直接但适用范围有限（物品数一多，组合数会爆炸式增长）的解题思路

重点内容

适用版本

桌面版通用（Excel 365 / 2021 / 2019 等）。

场景数据

5 件物品的重量和价值，以及背包的重量上限（放在 D6）：

物品	重量	价值
物品 1	12	4
物品 2	2	2
物品 3	1	2
物品 4	1	1
物品 5	4	10
背包限重	15	-

完整 VBA 代码

Dim limit As Double, weight As Double, value As Double, totalWeight As Double, maximumValue As Double
Dim i As Integer, j As Integer, k As Integer, l As Integer, m As Integer

limit = Range("D6").Value
maximumValue = 0

For i = 0 To 1
    For j = 0 To 1
        For k = 0 To 1
            For l = 0 To 1
                For m = 0 To 1

                    weight = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
                    value = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m

                    If value > maximumValue And weight <= limit Then
                        Range("B4").Value = i
                        Range("C4").Value = j
                        Range("D4").Value = k
                        Range("E4").Value = l
                        Range("F4").Value = m
                        totalWeight = weight
                        maximumValue = value
                    End If

                Next m
            Next l
        Next k
    Next j
Next i

Range("B6").Value = totalWeight
Range("B8").Value = maximumValue

代码说明

声明 limit（背包限重）、weight/value（当前组合的总重量/总价值）、totalWeight/maximumValue（目前找到的最优解），都用 Double 存小数；i 到 m 五个 Integer 变量，各自代表 5 件物品「要不要放进背包」（0 表示不放、1 表示放）
limit 从 D6 读入，maximumValue 初始化为 0（还没找到任何解）
用 5 层嵌套循环，每层都是 0 To 1，穷举 i、j、k、l、m 所有 0/1 组合，总共 2⁵ = 32 种可能的「放哪些物品」的方案
每种组合都用 12 * i + 2 * j + 1 * k + 1 * l + 4 * m 算出这个组合的总重量（每件物品的重量乘以「放不放」的 0/1），同理算出总价值
If value > maximumValue And weight <= limit Then 判断：这个组合的价值比目前记录的最优解更高，而且没有超重，才更新最优解——把这次的 i~m 写入 B4:F4（记录选了哪些物品），并更新 totalWeight、maximumValue
循环跑完全部 32 种组合后，B6 写入最优解的总重量，B8 写入最优解的最大价值

运行结果

最优解是选最后 4 件物品（物品 2、3、4、5，即 j=k=l=m=1，i=0），总重量 = 2+1+1+4 = 8（没有超过限重 15），总价值 = 2+2+1+10 = 15，是所有组合里价值最高且不超重的方案。

怎么运行

把 5 件物品的重量、价值和限重填入对应单元格，Alt + F11 打开 VBA 编辑器执行代码（或点命令按钮），B4:F4 会显示最优解选了哪些物品（1 = 选、0 = 不选），B6、B8 显示对应的总重量和最大价值。

学完你会

✅ 会用多层嵌套循环穷举所有「选或不选」的组合
✅ 会用一个变量随时记录并更新目前找到的最优解
✅ 理解暴力穷举法的组合数是 2 的物品数次方，物品一多就会跑不动

常见错误

这种写死 5 层循环的暴力穷举法只适合物品数很少的情况——每多一件物品，组合数就翻倍（2ⁿ），物品数一旦变多（比如 20 件以上），运算量会大到实际上跑不完，这是这个写法的局限，不是 bug
weight 和 value 的计算式里，每件物品的系数（重量、价值）是直接写死在公式里的数字，不是从单元格读取——物品数据一旦更动，VBA 代码里的数字也要手动同步改，否则算出来的还是旧数据的结果
If value > maximumValue And weight <= limit 里两个条件都要满足，若把 And 误写成 Or，会把超重的组合也当作候选最优解，选出不合法的答案

Sources

Blog / Website：

Knapsack Problem