algorithm - 给定一组元组(值，成本)，是否有一种算法可以找到存储给定数字的成本最低的元组组合

Question

我有一组 (value,cost) 元组，它们是 (2000000,200) , (500000,75) , (100000,20)

假设 X 是任意正数。

有没有一种算法可以找到可以存储X的值之和成本最低的元组组合。

元组值的总和可以等于或大于给定的 X

例如

给 x = 800000 答案应该是 (500000,75) , (100000,20) , (100000,20) , (100000,20)

给 x = 900000 答案应该是 (500000,75) , (500000,75)

给 x = 1500000 答案应该是 (2000000,200)

我可以对此进行硬编码，但集合和元组可能会发生变化，因此如果这可以用众所周知的算法替代，那就太好了。

Answer 1

这可以通过动态编程来解决，因为您对元组的数量没有限制并且可以负担得起提供数量的更高总和。

首先，您可以优化元组。如果一个大元组可以被多个具有相同或更低成本和相同或更高值(value)的较小元组替换，则您可以完全删除更大的元组。 此外，按降序按值(value)/成本对优化集中的元组进行排序对 future 的使用很有帮助。如果值(value)/成本更大，则元组更好。

时间复杂度 O(N*T)，其中 N 是优化元组值除以公因数 (F)，T 是优化元组集中的元组数。 内存复杂度 O(N)。

设置大小为 N 的数组 a 将包含:

• 在 a[i].cost 中 i*F 的最佳解决方案成本，0 表示特殊情况“尚无解决方案”
• 在a[i].tuple 中得到最佳解决方案的元组

递归方案:

• 函数将 n 作为单个参数获取 - 它为开始提供数字/F，为回避调用提供所需值的剩余/F 总和
• 如果n的数组a已满，返回a[n].cost
• 否则将 current_cost 设置为 MAXINT
• 从最好到最差的每个元组尝试将其添加到解决方案中:
• 如果 value/F >= n，我们有一些解决方案，将 tuple cost 与 current_cost 进行比较，如果更好，则更新 a[n].cost 和 a[n].tuple
• 如果 value/F < n，递归调用 n-value/F 并将成本与当前解决方案进行比较，如果需要，更新当前解决方案和 a[n].cost，a[n].tuple
• 毕竟return a[n].cost or throw exception是无解的

可以从 a 中检索元组列表，但在每一步遍历 .tuple。

可以将整个数组大小减小到最大(tuple.value/F)，但是您必须保存或多或少的完整解决方案，而不是为每个元素保存一个最佳 .tuple，并且您必须“滑动窗口”仔细。 与许多其他动态规划算法一样，可以将递归转化为从 0 到 n 的循环。