algorithm - 棘手的编程问题，我无法理解

Question

首先，让我说这不是家庭作业(我是一名 A-Level 学生，这与我们解决的问题相去甚远(这方式更难))，但更多我试图解决这个问题以改进我的编程逻辑。

我想到了一个场景，其中有一个随机整数数组，例如 10 个整数。用户将输入一个他想数到的数字，算法将尝试算出计算总和所需的数字。例如，如果我想从这个整数数组中得到总和 44:

myIntegers = array(1, 5, 9, 3, 7, 12, 36, 22, 19, 63);

输出将是:

36 + 3 + 5 = 44

或者类似的东西。我希望我说清楚。作为一个额外的好处，我想让算法选择尽可能少的数字来计算所需的总和，或者如果不能用提供的数字计算总和则给出错误。

我考虑过使用递归并遍历数组，一遍又一遍地添加数字，直到满足或超过总和。但我无法理解的是，如果算法超过总和并且需要选择从数组中选择哪些数字，该怎么办。

我不是在寻找完整的代码或完整的算法，我只是想知道您对我应该如何处理这个问题的意见，也许可以分享一些技巧或其他东西。我今晚可能会开始研究这个。 :P

正如我所说，不是作业。只是我想做一些更高级的事情。

感谢您提供的任何帮助。 :)

Answer 1

您正在查看 Knapsack Problem

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

---

编辑:您的特例是 Subset Sum Problem