Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I have no idea what you mean by "but the number seems to lose its 'context' as if add up the numbers (knapsack) strange combonations occur." You probably don't want to use really huge numbers (assuming int.Max is the largest number you can store as an "integer"), because there may be danger of overflow or roundoff problems. Why not use (m - bo)*q where m is just one more than the maximum buyout? –  Robert Israel Oct 7 '11 at 7:31
    
Forget about the the context. It seems (m-bo) is breaking the inversion of the buyout to most profit. If m is either mBO (max buyout) or maxInt (int.MaxValue) or mBO + 1 it breaks. –  mark_dj Oct 7 '11 at 8:20
    
do you have to use just 0-1 knapsack algorithm? If not, take a look at Hungarian algorithm, seems like very relevant to your problem –  com Oct 7 '11 at 14:37
    
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? –  mark_dj Oct 7 '11 at 18:09

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer
    
Yep, you are stating the problem 100% correctly. 0-1 knapsack is the right algorithm since it takes the weight and value variables. However I'm having problems inversing the value of the auction. Knapsack is about finding the 'highest' value combination till a threshold is reached. I want to find the 'lowest' value till a threshold is reached. That's why I try to inverse the buyout value, but without much success atm :) –  mark_dj Oct 8 '11 at 14:33
    
Note that your vague phrase "till a threshold is reached" has different meanings in both cases: for the knapsack problem the total weight may not be greater than the threshold, for your problem the total quantity may not be less than the threshold. In other words, quantity is a reversed weight, just as price is a reversed utility. Thus the reverse interpretation of selection: the items which will be bought are those that do not go into the knapsack. –  Florian Oct 8 '11 at 15:34
    
Interesting thought! Didn't think of that yet :) However what if the threshold is 200 and I only need 20? Even if they are cheap, you'll never need to use those 180. –  mark_dj Oct 8 '11 at 15:44
    
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. –  Florian Oct 8 '11 at 16:00

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

share|improve this answer

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

share|improve this answer
    
I am not suprised of the results in the example. My example is showing why it doesn't work. I am not expecting it to work that's why I ask ;) Anyway, my explanation of the problem seems to be fuzzled, I'll try to get a better example when I get home. –  mark_dj Oct 7 '11 at 13:52
    
I don't understand what you mean it doesn't work. The upper value has nothing to do with it, as it subtracts out. –  Ross Millikan Oct 7 '11 at 14:03
    
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. –  mark_dj Oct 7 '11 at 14:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.