3

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

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

和一个目标：

int target = 28;

我正在寻找一种算法来表示（允许重复）target中的元素总和，weights使得target匹配或超出，实现最接近的匹配target，并且在此范围内，使用的权重数量被最小化。

因此，对于上述输入，我希望返回10 20或15 15返回，因为30我们可以得到尽可能接近的结果，并且在 make 的选项中30，这两个都比10 10 10.

使用targetof 39，输出应该是20 20而不是，比如说，15 15 10或10 10 10 10。

使用 a target，14输出应该是15。

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

这不是家庭作业:)

4

2 回答 2

3

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

在您的示例weights中，两者之间都有 5 个“单元”，如果总是这样，问题将变得更容易解决。

于 2012-07-10T08:30:38.280 回答
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 测试

在此处输入图像描述

于 2012-07-10T09:16:07.013 回答