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 need to do some calculations in code but I'm not quite sure what the best mathematical approach is...

Say I have data like so:

Requirements:
-------------

Item 1: 100 units
Item 2: 45 units
Item 3: 45 units
Item 4: 15 units
Item 5: 40 units
Item 6: 150 units


Packages:
---------

Package 1:
Item 1: 20 units
Item 2: 10 units
Item 3: 8 units
Item 4: 2 units
Item 5: 0 units
Item 6: 30 units

Package 2:
Item 1: 13 units
Item 2: 5 units
Item 3: 15 units
Item 4: 0 units
Item 5: 15 units
Item 6: 20 units

Package 3:
Item 1: 25 units
Item 2: 10 units
Item 3: 0 units
Item 4: 3 units
Item 5: 18 units
Item 6: 20 units

What kind of algorithm/formula would I use to calculate what combination of products would get me closest to 100% of my requirement for each Item? It's OK to go slightly over/under on individual items since it won't always be possible to get to exactly 100% of each due to the varying amounts in each package - the calculation should calculate the 'closest possible' combination of packages.

I would also want the ability to add bias into the mix to account for stock/more expensive etc.. - for example, there is 10x more of package 1 in stock than package 2 so use more of package 1, or package 2 is 10x cheaper than 1 so use more of that.

In the end I would be able to use 'slider' type controls to affect the outcome for example if I slide the 'package 1 bias' up it would calculate with more of package 1 and less of the others - this part I can likely figure out on my own once I have a general idea of what type of calculation/algorithm I'll be doing...

Apologies for not using appropriate mathematical terms, I'm no mathematician.

EDIT: Even if you point me in the right direction that would help - I'm good at researching, I just don't know what kind of math terms I should be looking into.

share|improve this question
    
It might be an overkill, but take a look at linear programming. –  dtldarek Jan 31 '13 at 23:21
    
I believe this can be done with recursion and therefore probably dynamic programming –  user45150 Jan 31 '13 at 23:21
    
thanks I'll look into those methods. –  tsdexter Feb 1 '13 at 0:40

1 Answer 1

Your description of the problem is not as clear, but it is the well-known knapsack problem and is NP-complete. You can implement an approximation algorithm or the optimal if the problem instances are small enough in size to tolerate the computation time.

share|improve this answer
    
Thanks - this looks promising, researching it now. –  tsdexter Feb 1 '13 at 0:40
1  
@tsdexter Actually, finding that a problem is NP-complete is usually anything but promising. –  Rick Decker Feb 1 '13 at 1:15
    
@tsdexter you welcome. glad that helped. –  ashley Feb 1 '13 at 1:26
    
@ashley I'm having trouble fitting this into the Knapsack problem, which seems to be about maximizing 1 value while staying within the contraints of all the values, which is not quite what I want to do - I need to get as close as possible to all constraints - unless you can elaborate and explain where I'm going wrong? I've coded a solution to an unbounded knapsack problem and it won't quite do what I need as it really only cares about maximizing one of the contraints (item1 in this case) jsfiddle.net/tsdexter/knQ7G/1 - can it be modified for my case or is it not really a knapsack? –  tsdexter Feb 1 '13 at 20:01
    
@RickDecker thanks - I'm noticing that now. Any input on my above comment and knapsack solution? –  tsdexter Feb 1 '13 at 20:02

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.