Optimization algorithm in SQL

Question

Lets say I have a list of recipes, ingredients, and cost of these ingredients.

Could anyone point me in the right direction as to how I can starting with a budget of some dollar amount find the most numbers of recipes I can make?

For example

If I have $50 to spend And 5 recipes:

onion soup => ingredients (water $1, onion $45)
salad => ingredients (lettuce $4)
cake => ingredients (flour $8)
jello => ingredients (jello $4)
scambled eggs => ingredients (eggs $3)

How do I get sql to return a list like:

Combination number | recipes
-----------------------------
1                     1
1                     2
2                     1
2                     4
3                     1
3                     5

Just a quick comment: Do not try to do this in pure sql. If you are using MS SQL try to come up with some SQL CLR code. If you are doing Oracle, use Java. Better still, I would build an application on top of the database to handle the algorithm. Also, this looks to me like a problem where greedy would be useful, so try to learn about that technique. — Radu Caprescu
– Radu Caprescu, Commented Dec 2, 2012 at 18:54
Do you want the recipes or the largest number that you can make? — Gordon Linoff
– Gordon Linoff, Commented Dec 2, 2012 at 20:00

user330315 · Accepted Answer · 2012-12-02 19:39:58Z

1

You didn't specify a DBMS, so I'm assuming PostgreSQL:

with recursive all_combinations as (
  select array[name] as combination, 
         total_cost + 0.0 as combination_cost,
         id
  from recipe
  union all
  select a.combination || r.name,
         a.combination_cost + r.total_cost,
         r.id
  from recipe r
    join all_combinations a 
      on a.combination_cost + r.total_cost <= 50
     and not a.combination @> array[r.name]
     and r.id > a.id
)
select combination, combination_cost
from all_combinations
order by array_dims(combination), 1;

I'm not 100% sure it covers all combinations, though

Here is a SQLFiddle example: http://sqlfiddle.com/#!12/351be/4

answered Dec 2, 2012 at 19:39

user330315

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Optimization algorithm in SQL

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related