将一个整数表示为一些其他固定整数的和

Question

我有一个固定的重量列表：

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

并且有一个目标:

int target = 28;

我正在寻找一种算法，将target表示为从weights的元素之和（允许重复），使得target被匹配或超过，实现尽可能接近target，在此基础上，所使用的数量应该最小化。

因此，对于上述输入，我希望返回10 20或15 15，因为30是我们能够得到的最接近的数，而对于使30的选项来说，这两个比10 10 10更好。

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

对于target为14，输出应该是15。

除了常规的foreach循环，这里是否有一个更好的方法？我想检索数组中可用的最大值，并检查目标是否为负数，如果不是，则继续下一个值。

这不是作业 :)

- Eric Herlitz

---

我不理解“如果我的体重是39，结果将会是20和20”。数组中只有一个20。 - Tim Schmelter

那么，您可以从数组中多次选择相同的值，并且您希望所选值的总和大于或等于目标值。想必，您希望获得可能最低的总和，并且还要尽量减少所选值的数量？例如，当目标值为28时，选择10、10、10会更糟糕吗？ - Damien_The_Unbeliever

15,15 对于 28 来说同样有效，就像 20,10 一样。 - Eric Herlitz

@TimSchmelter - 我在我的第一个查询中涵盖了那种组合 - 除了其他限制条件，我们是否还在寻求最小化所做的选择数量？ - Damien_The_Unbeliever

大家好：我已经重写了代码，包括在评论中讨论的所有内容。@Trikks 请检查我是否没有改变问题。 - AakashM

Answer 1

这被称为背包问题，唯一的区别是你要寻找最近的匹配，而不是最接近的较低匹配。幸运的是，没有一个重量有不同的价值。困难在于你不能简单地使用其中一个最接近的weights，并使用剩余的值进行递归（较小值的组合有时会产生更好的匹配）。

在你的例子中，所有的weights之间都有5个"units"，如果这总是这种情况，那么问题将变得更容易解决。

- C.Evenhuis

Answer 2

多亏大家让我更明确了实际需求，我已经找到了解决方案。虽然代码不是最漂亮的，但这是MVP开发！

private static List<int> WeightsJuggle(List<int> packages, IOrderedEnumerable<int> weights, int weight)
{
    if (weight == 0)
        return packages;

    foreach (int i in weights.Where(i => i >= weight))
    {
        packages.Add(i);
        return packages;
    }

    packages.Add(weights.Max());
    return WeightsJuggle(packages, weights, weight - weights.Max());
}

我会将其翻译为：“我这样称呼它”。

IOrderedEnumerable<int> weights = new int[] { 10, 15, 20 }.OrderBy(x => x);
int weight = 65;
List<int> packages = new List<int>();

测试重量为65

测试重量为123

- Eric Herlitz

---

不正确的工作。尝试使用 weight = 30。结果将是 20, 15，但应该是 20, 10 或 15, 15 中的一个。 - sloth