Suppose we have k coupons to use.

Let the current set of cows you have selected thus far be S. Initially S is empty, and the greedy algorithm keeps on adding cows to S. We will prove that at each step, S is part of some optimal solution (i.e. there exists some optimal solution that contains S as a subset)

The base case is the empty set, which is trivially a part of any optimal solution.

For the inductive step, we assume that S is currently of some solution set. Now we want to add cow i. We want to show that S + i is also part of some optimal solution. There are two cases.

1. |S| < k. Thus cow i is cow with lowest C_i. Let T be some optimal solution that contains S as subset. Choose any cow j in T\S that is bought with coupon. Such j must exist since |S| < k and it's always best to use all coupons. Then cost of T-j+i <= cost of T, so choosing cow i is optimal as well.

2. |S| >= k. Thus, cow i is cow with min(P_i, C_i + (P_x — C_x)) for some x in S such that P_x — C_x is minimum. Again, consider some optimal solution T that contains S as subset.

Firstly, we look at the case where all cows in S hold on to their coupons (i.e. cows in S hold coupons according to current state of the greedy algorithm). This means no cow in T\S holds a coupon. Pick any cow j in T\S and swap that cow with cow i. Also, if P_i < C_i + (P_x — C_x), give the coupon of cow x to cow i. You can verify that this new arrangement has at least as low cost as T, thus selecting cow i is optimal.

Secondly, we look at the case where some cow y in S lost its coupon to some cow j in T\S. Swap cow i with cow j, and give the coupon of cow j to cow i. Again you can verify that this new arrangement is at least as good as T. Thus selecting cow i is optimal as well.

Thus we have completed proof of our inductive step.

I used a different solution for this problem. I don't know exactly why it works either, but it does since it passed all the tests.

What I did is the following: Insert into an array all the costs for all the cows together, both costs with coupons and without coupons and sort them by non-decreasing cost. Then iterate on the array and buy the cows greedily: you don't buy a cow only if your remaining money is not enough, if you have already bought this cow before with a coupon or if you have have no coupons left and this cost requires one.

I just came up with a solution off the top of my head right now, but it seems too simple.

I keep a sorted list of both P and C. Then I take the first element of each list and compare them. If P is less, it gets removed from that list and bought. If C is less, I apply the coupon to the most expensive cow (I pop the end of P and the beginning of C) and buy the cow at price C. Repeat until the next cow to be bought is larger than remaining money.

Is this correct? If not, why?