# What kind of algorithm/formula would I need to calculate how many items need to fill requirements?

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.

-
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

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.

-
Thanks - this looks promising, researching it now. – tsdexter Feb 1 '13 at 0:40
@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