自定义Knapsack算法代码错误排查及逻辑优化问询

DevOps 小满

2026-5-14

问题分析与修复方案

第一个问题：所有物品被替换为values第一个元素的原因

你的代码核心问题在于scores数组与原weights/values数组的索引脱节了。我们一步步拆解原例子的执行过程就能明白：

原输入：

weights = [1, 2, 4, 2, 5]
values = [5, 3, 5, 3, 2]
capacity = 10

计算出的scores是[4, 1, 1, 1, -3]，对应物品0到4的得分。

第一次循环：

找到最高得分4，scores.index(4)返回0，你把values[0]（即5）加入背包，重量变为1，然后scores.pop(0)，此时scores变成[1, 1, 1, -3]。

第二次循环：

找到最高得分1，scores.index(1)返回0，但这个0是当前scores数组的索引，而非原物品的索引！你却用它去访问原values数组，取到的是values[0]（还是5），而不是对应原物品1的values[1]（3）。

之后每次循环都会重复这个错误：scores数组的索引已经和原物品的索引不匹配，但你始终用当前scores的索引去取原values数组的值，导致每次都拿到第一个物品的value5。

修复第一个问题的方法

我们需要跟踪每个得分对应的原物品索引，而不是单独维护scores数组。可以把每个物品的得分、重量、价值、原索引打包成元组，再进行操作：

def knapsack(weights, values, capacity):
    # 打包每个物品的(得分, 重量, 价值, 原索引)，用负分实现降序排序
    items = []
    for i in range(len(values)):
        score = values[i] - weights[i]
        items.append( (-score, weights[i], values[i], i) )
    # 按得分降序排序（得分高的在前）
    items.sort()
    knapsack = []
    total_weight = 0
    for item in items:
        _, w, v, idx = item
        if total_weight + w <= capacity:
            knapsack.append(v)
            total_weight += w
    return knapsack

# 测试原例子
weights = [1, 2, 4, 2, 5]
values = [5, 3, 5, 3, 2]
capacity = 10
print(knapsack(weights, values, capacity))  # 输出 [5,5,3,3]，总重量1+4+2+2=9 <=10

这个版本通过打包原索引，确保每次操作都能正确关联到对应的物品重量和价值，不会再出现取错值的问题。

第二个问题：得分相同时的选择逻辑缺陷

你的第二个测试用例：

weights = [8, 2, 6, 7, 9]
values = [3, 11, 13, 7, 4]
capacity = 24

计算得分：

物品0：3-8=-5
物品1：11-2=9
物品2：13-6=7
物品3：7-7=0
物品4：4-9=-5

按原贪心逻辑，得分相同的物品0和4会按原顺序被处理，优先选物品0（重量8），但加入后总重量是2+6+7+8=23，剩余1无法利用；而选物品4（重量9）的话，总重量是2+6+7+9=24，刚好填满，总价值也更高（35 vs 34）。

问题根源

你的贪心策略仅以value - weight作为唯一排序依据，但当得分相同时，这个指标无法区分哪个物品更适合剩余容量。此外，value - weight本身并不是0-1背包问题的最优贪心指标（常用的更优指标是单位重量价值value/weight，但即使是这个指标也不能保证得到0-1背包的全局最优解，这是贪心算法的局限性）。

修复思路

我们需要在排序时增加次级排序规则，当得分相同时，优先选择：

单位重量价值更高的物品；
或者价值更高的物品；
或者更匹配剩余容量的物品。

针对你的测试用例，这里给出结合得分+单位重量价值的优化版本：

def knapsack(weights, values, capacity):
    items = []
    for i in range(len(values)):
        score = values[i] - weights[i]
        # 计算单位重量价值（避免除以0的情况）
        value_per_weight = values[i] / weights[i] if weights[i] != 0 else float('inf')
        # 排序优先级：得分降序 > 单位重量价值降序 > 价值降序
        items.append( (-score, -value_per_weight, -values[i], weights[i], values[i], i) )
    # 升序排序等价于按原优先级降序排列
    items.sort()
    knapsack = []
    total_weight = 0
    for item in items:
        _, _, _, w, v, idx = item
        if total_weight + w <= capacity:
            knapsack.append(v)
            total_weight += w
        # 填满背包后提前退出
        if total_weight == capacity:
            break
    return knapsack

# 测试第二个例子
weights = [8, 2, 6, 7, 9]
values = [3, 11, 13, 7, 4]
capacity = 24
print(knapsack(weights, values, capacity))  # 输出 [11,13,7,4]，总重量2+6+7+9=24，总价值35

这个版本中，当得分相同时，会优先选择单位重量价值更高的物品（物品4的单位价值≈0.44，物品0的单位价值=0.375，所以物品4排在前面），这样就能选中物品4，刚好填满背包，得到更高的总价值。

额外说明

需要注意的是，贪心算法对于0-1背包问题无法保证得到全局最优解，它只能得到一个较优的近似解。如果需要绝对最优解，你需要使用动态规划（DP）方法。

内容的提问来源于stack exchange，提问作者Aryamaan Goswamy

自定义Knapsack算法代码错误排查及逻辑优化问询

第一个问题：所有物品被替换为values第一个元素的原因 #

修复第一个问题的方法 #

第二个问题：得分相同时的选择逻辑缺陷 #

问题根源 #

修复思路 #