使用提供的度量单位以最小超额拟合目标总和的算法

Question

下面是一个例子：

客户订购 57 个单和平项目。该公司只销售 15 和 6 的单位。

该算法必须按重要性顺序找出具有以下优先级的UOM(度量单位(的最佳组合

1. 最少的超额量
2. 使用最高度量单位

在此示例中，预期结果List<int>：

{ 15， 15，

15， 6， 6 }//sum=57

我研究过"垃圾箱包装"和"背包问题"，但无法弄清楚在这种情况下如何应用它。

到目前为止，我有这个显然没有完成最佳组合。

void Main()
{
var solver = new Solver();
var r  = solver.Solve(57, new decimal [] {6, 15}).Dump();
}
public class Solver
{
public List<decimal> mResults;
public List<decimal> Solve(decimal goal, decimal[] elements)
{
mResults = new List<decimal>();
RSolve(goal, 0m, elements, elements.Where(e => e <= goal).OrderByDescending(x => x).FirstOrDefault());
return mResults;
}

public void RSolve(decimal goal, decimal currentSum, decimal[] elements, decimal toAdd)
{
if(currentSum >= goal)
return;
currentSum += toAdd;
mResults.Add(toAdd);
var remainder = goal - currentSum;

var nextToAdd = elements.Where(e => e <= remainder).OrderByDescending(e => e).FirstOrDefault();
if(nextToAdd == 0)
nextToAdd = elements.OrderBy(e => e).FirstOrDefault();
RSolve(goal, currentSum, elements, nextToAdd);
}
}

Answer 1

这是变革问题的一个实例。它可以通过动态规划来解决;构建一个数组，其中索引 i 处的值是可用于总计i的解决方案的最大硬币，如果没有解决方案，则为 -1。如果首先使用较大的单位，则解决方案将自动满足"最高计量单位">要求;为了满足"最少的超额量">要求，您可以尝试找到 57 的解决方案，如果这不起作用，请尝试 58，依此类推。

运行时间最多为 O((n +1 - n₀(k(，其中 n 是所需的总和，n₀ 是缓存中的最大索引，k是度量单位的数量。特别是，在尝试 57 之后，尝试 58 最多需要 O(k( 时间，然后最多需要 O(k( 时间尝试 59，依此类推。

要为总和 n 构建输出列表，请初始化一个空列表，然后在 n> 0 时将值附加到缓存中的索引 n 处，并从n中减去该值。