以最小代价划分为n个bins
Divide to n bins with minimum cost
- 考虑
2*k 元组 (a0, b0), (a1, b1), ... 和 2 个 bin A 和 B。将 i-th 元组放入 bin A 将花费你 ai 美元，在 bin B 中将花费你 bi 美元。在 bin A 中放置 k 个元素，在 bin B 中放置 k 个元素的最低成本是多少。
我想到了贪心算法：对元组数组进行排序，以abs(ai - bi)为关键字，降序排列。但是，我们可以使用动态规划来解决这个问题吗？如果有 n 个垃圾箱而不是两个呢？
设dp[i][j]为将j元素放入bin A中前i个元素的最小代价，例如dp[0][0]为将0个元素放入A中的前0个元素的最小代价； dp[4][2] 是将 2 个元素放入 A 中前 4 个元素的最小成本
那么：对于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]
- 考虑
2*k元组 (a0, b0), (a1, b1), ... 和 2 个 bin A 和 B。将i-th元组放入 binA将花费你ai美元，在 binB中将花费你bi美元。在 bin A 中放置k个元素，在 bin B 中放置k个元素的最低成本是多少。
我想到了贪心算法：对元组数组进行排序，以abs(ai - bi)为关键字，降序排列。但是，我们可以使用动态规划来解决这个问题吗？如果有 n 个垃圾箱而不是两个呢？
设dp[i][j]为将j元素放入bin A中前i个元素的最小代价，例如dp[0][0]为将0个元素放入A中的前0个元素的最小代价； dp[4][2] 是将 2 个元素放入 A 中前 4 个元素的最小成本
那么：对于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]