如何摆脱暴力的背包？

Question

为了即将到来的考试，我一直在研究动态规划的一些问题，背包似乎是开发一个基本水平上可以理解的解决方案的一个很好的切入点

我有一个解决方案，可以生成一个答案，但它不是有效的，因为运行时太高了，我如何实现递归到这个

  return knapsack_recursive(profits, weights, capacity, 0)


def knapsack_recursive(profits, weights, capacity, currentIndex):
  if capacity <= 0 or currentIndex >= len(profits):
    return 0

  profit1 = 0
  if weights[currentIndex] <= capacity:
    profit1 = profits[currentIndex] + knapsack_recursive(
      profits, weights, capacity - weights[currentIndex], currentIndex + 1)

  profit2 = knapsack_recursive(profits, weights, capacity, currentIndex + 1)

  return max(profit1, profit2)


def main():
  print(solve_knapsack([1, 6, 10, 16], [1, 2, 3, 5], 7))
  print(solve_knapsack([1, 6, 10, 16], [1, 2, 3, 5], 6))


main()

Answer 1

根据维基百科：“背包问题的决策问题形式（是否可以在不超过权重W的情况下获得至少V的值）是NP完全的，因此在所有情况下都没有正确和快速（多项式时间）的已知算法。”

因此，不存在保证在可处理的时间内找到最优解的算法。超过一定的规模，就不能用当前的计算能力来完成

然而，使用启发式可以找到好的解决方案：可以使用一种好的策略，例如选择每单位重量最有价值的物品，首先从最大的物品开始，然后用较小的物品填补空白

由于这个问题已经得到了广泛的研究，你会发现很多关于不同算法的论文

除非你被明确地要求去设计一个递归算法