I thought you were right but actually no, you'd need more assumptions. Consider this example: Type A: coupon a1 has cost 1, value 2. coupon a2 has cost 2, valu

I thought you were right but actually no, you'd need more assumptions. Consider this example: Type A: coupon a1 has cost 1, value 2. coupon a2 has cost 2, value 3.99. Type B: coupon b1 has cost 1, value 1. We have 100 people of Type A and 100 people of Type B. The total budget is 200. The optimal solution is to pick all Type A people, coupon a2, for a value of 399. Greedy picks all Type A people, coupon a1, and then all Type B people, coupon b1, for a value of 300.