Divide to n bins with minimum cost

Question

1. Consider 2*k tuples (a0, b0), (a1, b1), ... and 2 bins A and B. placing the i-th tuple in bin A will cost you ai dollar, in bin B will cost you bi dollar. What the minimum cost to place k elements in bin A and k elements in bin B.

I came up with the greedy algorithm: sort the tuples array, taking abs(ai - bi) as key, in descending order. However, can we solve this problem by using dynamic programming? What if there are n bins instead of two.

Answer 1

Let dp[i][j] be minimum cost when put j element in bin A for the first i elements, e.g., dp[0][0] is the minimum cost to put 0 elements in A for the first 0 elements; dp[4][2] is the minimum cost to put 2 element in A for the first 4 elements

Then: For the ith element (index is i - 1 so I use b[i - 1] and a[i - 1]), we need to put it in either bin A or bin B. So we calculate the min of two cases:

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

Then the problem is to get dp[2*k][k]