I am programming a bargain composer. The composer tries buy the cheapest auctions till the specified quantity is reached. A auction has two important properties. Quantity and Buyout price. I use the 0-1 knapsack algorithm to cope with this problem. I choose this algorithm, because it can takes the quantity and a value list.
A better algorithm suited for this job is also welcome :)
Problem I am having problems to calculate the value list. The buyout price is not the value you want to put on the 0-1 knapsack. It would return the most expensive items. So I need to inverse the value list. However a BO * -1 would't work since my 0-1 knapsack implementation doesn't work with negative values.
Substracting from a value would inverse the buyout value aswell, however the question from what value? I've tried the max buyout value of the list itself, but it is really a wild guess since I don't really know how to approach this problem (low math experience :<). The following formula works till you hit the maxValue item itself
0 * q = 0
$$P = (maxBO - bo) * q$$
- P = inversed buyout value
- maxBO = maximum buyout in the current list of auctions
- bo = buyout
- q = quantity
Edit: Removed the confusing example. Clarified the problem