Algorithm to purchase maximum items

Question

We are having N gold coins and M silver coins. There are k items each having some cost, A gold coins and B silver coins, where A or B can be zero also.

What can be algorithm to purchase maximum number of items?

Answer 1

In this problem, every item has a two dimensional cost. Let item i have cost c[i] = < a, b > where a is the cost in gold coins and b in the cost of silver coins.

The items can now be partially ordered so that item i is 'not-more-expensive' than item j if

c[i] = <a, b>    c[j] = <a', b'>  and    a <= a' AND b <= b'

Note that this is a partial order. Two items <1, 2> and <2, 1> are not comparable in this partial ordering; neither one is not-more-expensive than the other.

It is now clear that a greedy algorithm can safely buy items as long as they are 'not-more-expensive' compared to every other item remaining, but when there are multiple non-comparable items available, more analysis (e.g. search) can be needed.

For example, if the costs are

 <1, 1>
 <2, 1>
 <1, 2>
 <3, 3>

this results in this partial order:

        <1, 1>
       /      \
     <2, 1>   <1, 2>
         \   /
         <3, 3>

(most expensive item on the bottom). A greedy algorithm would purchase first <1, 1>. After that, both <2, 1> and <1, 2> are viable purchasing options. If the algorithm chooses to buy <2, 1>, the next to buy is then <1, 2> because it is now not-more-expensive than all other remaining items (<3, 3>).

Simple greedy algorithms can fail. With the setup <2, 1>, <1, 2>, <3, 0> and initial amount of coins gold = 4, silver = 2, the optimal solution is to by <1, 2> and <3, 0>, but buying <2, 1> first leads to being able to purchase only that item (purchases is left with <2, 1> coins that doesn't allow to buy any of the two remaining items).

I would approach this buy building the partial order structure and then performing a backtracking search. If time constraints wouldn't allow for full backtracking, I would use limited backtracking as a heuristics for an otherwise greedy algorithm.