c# - 将一个整数表示为其他一些固定整数的总和

Question

我有一个固定的权重列表:

int[] weights = new int[] { 10, 15, 20 };

和一个目标:

int target = 28;

我正在寻找一种算法来将 target 表示为 weights 中元素的总和(允许重复)，这样 target 要么匹配或超过，实现与目标最接近的匹配，并且在其中，使用的权重数量被最小化。

因此，对于上述输入，我希望返回 10 20 或 15 15，因为 30 尽可能接近得到，在制作30的选项中，这两个比10 10 10好。

对于 39 的 target，输出应该是 20 20 而不是 15 15 10 或 10 10 10 10。

target 为 14，输出应为 15。

除了常规的 foreach 循环之外，这里还有什么好的方法吗？我正在考虑检索数组中可用的最大值并检查目标是否为负数，如果不是则让我们寻找下一个值。

这不是作业:)

Answer 1

这被称为 knapsack problem .唯一的区别是您正在寻找最近 匹配，而不是最近较低 匹配。同样幸运的是，没有一个权重具有不同的值。困难在于您不能简单地使用最接近的 权重 之一并使用剩余值递归(较小值的组合有时会更好地匹配)。

在您的示例中，权重 之间都有 5 个“单位”，如果始终如此，问题将变得更容易解决。