postgresql - SQL中的优化算法

Question

假设我有一份食谱、配料和这些配料成本的清单。

谁能指出我正确的方向，如何从一些美元的预算开始找到我能做的最多的食谱？

例如

如果我有 50 美元可以花 5 个食谱：

1. 洋葱汤 => 配料（水 1 美元，洋葱 45 美元）
2. 沙拉 => 配料（生菜 4 美元）
3. 蛋糕 => 配料（面粉 8 美元）
4. 果冻 => 配料（果冻 4 美元）
5. 炒鸡蛋=>配料（鸡蛋3美元）

如何让 sql 返回如下列表：

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

Answer 1

您没有指定 DBMS，所以我假设 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;

不过，我不是 100% 确定它涵盖了所有组合

这是一个 SQLFiddle 示例：http ://sqlfiddle.com/#!12/351be/4