用最小的成本分成n个垃圾箱

Question

1. 考虑2*k元组(a0，b0)，(a1，b1)，.2桶A和B。把i-th元组放在bin A中将花费ai美元，在bin B中花费bi美元。在bin A中放置k元素和在bin B中放置k元素的最低成本是多少？

我提出了一个贪婪的算法:按降序对元组数组进行排序，以abs(ai - bi)作为键。但是，我们能否用动态规划来解决这个问题呢？如果有n回收箱而不是两个。

Answer 1

对于第一个I元素，当在bin A中放置j元素时，dp[i][j]是最小成本，例如，对于前4个元素，dp[0][0]是将0元素放入A中的最小成本；dp[4][2]是将2个元素放入A中的最小成本。

然后:对于ith元素(索引是i - 1，所以我使用b[i - 1]和a[i - 1])，我们需要将其放入bin A或bin B中，因此我们计算了两种情况的最小值：

dp function: dp[i][j] = Math.min(dp[i - 1][j] + b[i - 1], dp[i][j - 1] + a[i - 1])

那么问题是如何获得dp[2*k][k]