SQL 背包问题

SQL 背包问题

4 years ago

source link: https://my.oschina.net/u/4600992/blog/4830587
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

SQL 背包问题 - SQL必知必会的个人空间 - OSCHINA - 中文开源技术交流社区

这是一道简化的背包问题：有一背包能容纳 50kg 的物品，现有 9 种物品（它们的重量分别是5kg、8

kg、20kg、35kg、41kg、2kg、15kg、10kg、9kg），要刚好能装满背包，有多少种物品组合？

由于要用到 SQL 来处理，我们先把上面的物品的重量的数据存到表中，并给每种物品分配一个编号。物品表 bag 的数据如下：

id         num  
------  --------
001            5
002            8
003           20
004           35
005           41
006            2
007           15
008           10
009            9

我们的解题思路也是非常简单、粗暴，就是把所有物品的可能的组合的重量都算出来，最后只取总量是 50kg 的组合。当然，在这个过程中可以做些优化的工作。

那怎么求组合呢？用自关联。比如，求任意两种物品的组合，SQL 可以这么写：

SELECT 
  * 
FROM
  bag a,
  bag b 
WHERE a.id < b.id

条件 a.id < b.id 用于去掉重复的组合。比如，物品 001 和物品 002，不管是 001 & 002 或者 002 & 001 ，都属于一个组合。

我们可以像上一篇文章一样，使用递归枚举出所有的组合。

WITH RECURSIVE t (id, total, path, formula, next_id) AS 
(SELECT 
  id,
  num AS total,
  CAST(id AS CHAR(100)) AS path,
  CAST(num AS CHAR(100)) AS formula,
  id AS next_id 
FROM
  bag 
UNION ALL 
SELECT 
  t.id,
  t.total + a.num AS total,
  CAST(
    CONCAT(t.path, ' & ', a.id) AS CHAR(100)
  ) AS path,
  CONCAT(
    formula,
    ' + ',
    CAST(num AS CHAR(100))
  ) AS formula,
  a.id AS next_id 
FROM
  t,
  bag a 
WHERE t.next_id < a.id 
  AND t.total + a.num <= 50) 
SELECT 
  formula,
  total,
  path 
FROM
  t 
WHERE total = 50

其中，字段 path 和 formula 只是为了让结果看起来更友好，去掉它们对整个计算过程没有影响。

关键的处理逻辑是这段代码：

WITH RECURSIVE t (id, total, next_id) AS 
(SELECT 
  id,
  num AS total,
  id AS next_id 
FROM
  bag 
UNION ALL 
SELECT 
  t.id,
  t.total + a.num AS total,
  a.id AS next_id 
FROM
  t,
  bag a 
WHERE t.next_id < a.id 
  AND t.total + a.num <= 50)

total 是组合中的数值加和的结果，条件 t.next_id < a.id 是为了保证组合中的物品的编号按一定的顺序（从小到大）排序，防止出现重复的组合；条件 t.total + a.num <= 50 提前过滤掉不满足的组合，减少计算的次数。

最终的输出结果 >>>

formula               total  path                         
-------------------  ------  -----------------------------
35 + 15                  50  004 & 007                    
41 + 9                   50  005 & 009                    
5 + 35 + 10              50  001 & 004 & 008              
5 + 8 + 35 + 2           50  001 & 002 & 004 & 006        
5 + 20 + 15 + 10         50  001 & 003 & 007 & 008        
5 + 8 + 20 + 2 + 15      50  001 & 002 & 003 & 006 & 007

Recommend