1
$\begingroup$

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

  • 0
    No I am not bound to that. However I am filling up bag (till a certain) amount and I am trying to find the cheapest items. How would Hungarian algorithm fit in the quantity aka weight value?2011-10-07

3 Answers 3

3

First to make sure that I understood the problem correctly, I state it in my own words: It is about buying a certain quantity of a commodity, and there is a set of traders who offer the commodity in their individual quantity for their individual price, and you want to find a subset of the set of traders such that the sum of their quantities is at least the required quantity, and the sum of prices is as small as possible.

Is this the problem you want to solve? If so, this is exactly a knapsack problem (selecting items with specified weight and utility such that the sum of weights is at most a given threshold and the sum of utilities is as large as possible) if you interpret selecting items for the knapsack as not buying them.

  • 0
    Of course as the knapsack weight threshold you have to use the total quantity of all offers minus the requested quantity. So again, price --> utility; quantity --> weight; total quantity minus required quantity --> weight threshold; items to buy --> items not put into the knapsack; items not to buy --> items to put into the knapsack.2011-10-08
1

I found the formula:

$inverseBuyout = (2 * ( 1 / ( buyout / quantity ))) * quantity$

simplified:

$inverseBuyout = {\frac{2\cdot quantity^2}{buyout}}$

Thanks to: http://www.khanacademy.org/video/direct-and-inverse-variation?playlist=Algebra

0

It is true item 2 plus item 3 costs more than item 1. You have item1=10*int.Max-5000, item2=5*int.Max-500, item3=5*int.Max-2000, so item2 + item3 - item1 = 2500. Why do you find this surprising? I don't understand

It seems (m-bo) is breaking the inversion of the buyout to most profit. If m is either maxBO (max buyout) or int.Max or mBO + 1 it breaks.

at all

  • 0
    I am using knapsack as algorithm for picking the best items. The algorithm works with 2 lists. A weight and a value list. The weight is quantity and I can't figure out how to calculate the value list with the set of properties I have atm (Quantity, Buyout). I can't compose the cheapest combination (since you don't want to select the most expensive items). That's why I try to inverse the buyout with (maxVal-buyout) and multiple it with the quantity.2011-10-07