背包问题：将所有项目替换为值

Question

我正在尝试通过应用自己的算法来解决背包问题。我给每个项目打一个分数（值[i]-权重[i]），并将高分的项目添加到背包中。但是此代码用值的第一项（5）替换了每个项。

def knapsack(weights, values, capacity):
  knapsack = []
  scores = []
  for i in range(len(values)):
    score = values[i] - weights[i]
    scores.append(score)
  weight = 0
  while weight < capacity:
    if len(scores) != 0:
      valuable = max(scores)
      knapsack.append(values[scores.index(valuable)])
      weight += weights[scores.index(valuable)]
      scores.pop(scores.index(valuable))
    else:
      break
  return knapsack

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

print(knapsack(weights, values, capacity))

此代码有什么问题？

编辑：大家好，我已修复它，但似乎存在逻辑错误。如果：

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

然后有两个得分相同的物品（8、3和9、4），但是9、4更好，因为它正好适合背包，并且具有较高的价值。即使将第8行更改为<=也无济于事。

Answer 1

该数据集的分数恰好是降序排列，因此，当您将分数从列表中弹出时，最有价值的商品的索引始终为索引0。由于在将值添加到背包时也不会从起始列表中弹出值，因此始终将第0个项目添加到背包。

从背包中将其从初始列表中弹出时，它将按顺序添加所有值。

knapsack.append(values.pop(scores.index(valuable)))

注：仍然存在一个错误，因为不应添加最后一个值。您仅在循环情况下检查背包是否未满。您需要在将商品添加到麻袋之前进行检查，以确保该商品不会使它翻倒。

Answer 2

您也不会从列表中删除附加值。尝试添加

values.pop(scores.index(valuable))
weights.pop(scores.index(valuable))

到scores.pop(...)之前的行。

另外，如果添加的项目会使您超出容量，则需要跳出循环，例如：

if (weight + weights[scores.index(valuable)]) > capacity:
    break

您需要处理平局决胜的代码，这会将得分索引重新分配到容量允许的最高值项目，例如：

ties = [i for i, x in enumerate(scores) if x == valuable]
if len(ties) > 1:
    most_valuable = -1
    for idx in ties:
        if values[idx] > most_valuable and (weight + weights[idx]) <= capacity:
            most_valuable = values[idx]
            scores_idx = idx

完整代码：

def knapsack(weights, values, capacity):
    knapsack = []
    scores = []
    for i in range(len(values)):
        score = values[i] - weights[i]
        scores.append(score)
    weight = 0
    while weight < capacity:
        if len(scores) != 0:
            valuable = max(scores)
            scores_idx = scores.index(valuable)
            ties = [i for i, x in enumerate(scores) if x == valuable]
            if len(ties) > 1:
                most_valuable = -1
                for idx in ties:
                    if values[idx] > most_valuable and (weight + weights[idx]) <= capacity:
                        most_valuable = values[idx]
                        scores_idx = idx
            if (weight + weights[scores_idx]) > capacity:
                break
            knapsack.append(values[scores_idx])
            weight += weights[scores_idx]
            values.pop(scores_idx)
            weights.pop(scores_idx)
            scores.pop(scores_idx)
        else:
            break
    return knapsack

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

print(knapsack(weights, values, capacity))