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.

So I just remembered Lincoln Logs exist, so I found ten giant sets of them on ebay for Buy It Now, and I'm trying to decide what combination of purchases gives me the most logs for the least money if I'm going to purchase $n$ sets.

Then I remembered this is exactly the sort of thing I learned in algorithms class, but I really don't want to set this up myself. Much, much too lazy on this rainy day. Are there any online or downloadable calculators which let me set it up easily?

share|improve this question
    
I'm not sure what you're asking exactly, but I will vote this up if only for Lincoln Logs. Could you comment on the 'giant'ness of the sets? Are they equally huge? Are you having some combination of bidding and buying now? –  Ian Coley Mar 20 '13 at 0:09
    
Given that I am purchasing $n$ sets of logs which have {cost, number of logs} from the set ( {20, 120}, {45, 300}, {30, 220}, etc ), which $n$ sets should I purchase in order to maximize the ratio of logs acquiredd to money spent? –  Aerovistae Mar 20 '13 at 0:11
1  
@FrankMcGovern, your unclosed comment is messing up the page. Please delete it. –  Gerry Myerson Mar 20 '13 at 1:50
1  
But seriously I think this is a site bug that needs to be MetaSO posted, so don't just delete it-- all of the comments under this question are going beyond their assigned HTML element and overlapping into the community bulletin, at least on my screen. –  Aerovistae Mar 20 '13 at 2:11
1  
@FrankMcGovern: it's fixed. –  robjohn Mar 20 '13 at 3:24

2 Answers 2

The search term you want is "Knapsack Problem".

http://en.wikipedia.org/wiki/Knapsack_problem

There are some interactive ones online,

https://www.google.com/#q=knapsack+problem+solver

As you remembered, this is in principle equivalent to CSP's, or any other NP-complete problem.

share|improve this answer

For each set, you can figure the logs/money ratio. Can you buy multiples of one type? If so, just buy as many as you want of the best. If not, buy the best one, and keep going down until you have spent as much as you want. If you have some money left over, look down to see if any small cheap sets are out there and think about those.

share|improve this answer
    
Maximizing (logs per money) can be in tension with maximizing (money spent), though. –  zyx Mar 20 '13 at 1:56
    
@zyx: If you want to maximize money spent, buy them all. If the best logs per money is outside your budget, exclude it and go on to the next. There could be an issue if the best logs/money almost exhausts your budget and all you can afford after that is a bad bargain. Say you are offered $(100,50), (60,31),(58,31),(3,10)$ and have $62$ to spend. You can get $118$ taking the middle two and only $103$ taking the top and bottom. But you can get $100$ and still have $12$ in your pocket, which might be the best choice. These problems are theoretically hard and practically easy. –  Ross Millikan Mar 20 '13 at 2:03
    
The greedy algorithm attains at least half the optimum result (given unlimited inventory). I was thinking of situations where buying one unit of the most efficient thing eats up 51 percent of the budget, but there are several nearly as efficient things that each cost 49.9 percent of the budget, and nothing else to buy. Buying the best thing first blocks the ability to buy much more of a nearly as good thing. –  zyx Mar 20 '13 at 2:18
    
@zyx: you are right, that could happen. If the number of choices is small, as here, it will be obvious what is going on. You can assess a small number of alternatives and see the best answer depending on your priorities. –  Ross Millikan Mar 20 '13 at 2:23
    
Well, if you believe the market drives the prices to some sort of equilibrium, then real-life optimization should be complicated, with obvious imbalances already having been accounted for. I grant that this is often violated. –  zyx Mar 20 '13 at 2:31

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.