Maximum sum combination
Often it is the case that reformatting the data leads to insights. Let's take a look at the test case:

A: 1 2 3 4 5
B: 5 4 3 2 1


Now let's suppose that we subtract the smaller of each pair from both, and take the sum of the smallers:

A: 0 0 0 2 4
B: 4 2 0 0 0


If we can find the maximum tips available in this problem, the real result will be that amount plus 1 + 2 + 3 + 2 + 1.

Can you now see how to solve the problem more easily?

Unfortunately it appears that the tags are misleading; dynamic programming does not buy you much, but a greedy algorithm does.


  Your greedy algorithm works out for that test-case. I'm not sure if it works in general. Could you expand a bit on the intuition?


First off, it should be clear that we can always reduce the problem to one where the columns are of this form where one or both are zero; "subtract the smaller from both" always works.

So the problem now is: we must choose up to X numbers from row A, and up to Y numbers from row B, such that their sum is maximized.

The proposed algorithm is: always take the largest number remaining. Suppose we have:

A: 0 0 2 1 5  -- choose up to 2
B: 4 2 0 0 0  -- choose up to 4


We now have to make assignments, and we do it in order from highest to lowest benefit. Start with the biggest bang:

           A
A: 0 0 2 1 5  
B: 4 2 0 0 0  


Then the next:

   B       A
A: 0 0 2 1 5  
B: 4 2 0 0 0  


Now we have a tie, so pick both:

   B B A   A
A: 0 0 2 1 5  
B: 4 2 0 0 0  


And now we've exhausted A, which leaves

   B B A B A
A: 0 0 2 1 5  
B: 4 2 0 0 0  


What's the intuition that the greedy algorithm works?  Examine the first choice. If, say, we gave Bob the 5/0 delivery and take the zero tip, what does that get us? It only gives Andy the opportunity to make the lower-valued "1/0" delivery later on, which is not a win; we've given up five to gain one.