用最小成本将数据分成n个桶

Question

考虑2*k个元组(a0, b0)，(a1, b1)…和2个容器A和B，将第i个元组放入容器A将花费ai美元，放入容器B将花费bi美元。将k个元素放入容器A和k个元素放入容器B的最小成本是多少。

我想到了贪心算法：按降序排序元组数组，以abs(ai-bi)作为键。然而，我们能否通过使用动态规划来解决此问题？如果不是两个而是n个容器，该怎么办？

- FakeQuantum

---

嗨，请参考此页面以提出好问题，这些问题通常会得到赞同，从而有助于获得好答案。如何提出一个好问题？ - v8-E

你能解释一下你是如何使用排序结果来填充箱子的吗？以及这如何保证总成本最小化？ - trincot

提示：从底部向上思考。考虑填充最后一个箱子，它必须是A或B。假设它是B。那么B的剩余元组为k-1，而A的剩余元组为k。或者如果是A，则A的剩余元组为k-1，B的剩余元组为k。因此，填充最后一个箱子的最小成本是cost（B的k-1个元组，A的k个元组）+ bi，cost（B的k个元组，A的k-1个元组）+ ai的最小值，现在考虑递归实现，然后进行记忆化。 - SomeDude

@trincot 你可以通过将排序后的列表分成两部分来使用它。至于为什么它是最好的，请考虑其他任何划分。从中按任意顺序取出它们，以获取未排序的列表。使用冒泡排序对其进行排序，并跟踪划分。每次交换要么保持代价不变（在bin内部交换），要么降低代价（跨越bin边界）。直到停在这个时刻为止。因此，没有其他的划分方式可以更好。 - btilly

@btilly，感谢您的评论，但我实际上是想让OP澄清他们的问题。从他的问题中我们无法知道他对排序结果做了什么，而在问题中提到这一点似乎很相关。 - trincot

Answer 1

让 dp[i][j] 表示前 i 个元素放入 A 中放置 j 个元素的最小成本，例如，dp[0][0] 是前 0 个元素放入 A 中放置 0 个元素的最小成本；dp[4][2] 是前 4 个元素放入 A 中放置 2 个元素的最小成本。

然后：对于第 i 个元素（索引为 i - 1，因此使用 b[i - 1] 和 a[i - 1]），我们需要将其放入 A 或 B 中。因此，我们计算两种情况的最小值：

dp 函数：dp[i][j] = Math.min(dp[i - 1][j] + b[i - 1], dp[i][j - 1] + a[i - 1])

然后问题就是获取 dp[2*k][k]。

- Thomas

---

关于效率的说明。这是O(k^2)。将其自然推广到n个桶将会是O(k^n)。对于n=2，贪心算法更好。 - btilly