首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >SQL 背包问题

SQL 背包问题

作者头像
白日梦想家
发布2021-01-02 17:06:59
7070
发布2021-01-02 17:06:59
举报
文章被收录于专栏:SQL实现SQL实现

这是一道简化的背包问题:有一背包能容纳 50kg 的物品,现有 9 种物品(它们的重量分别是 5kg、8kg、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  
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-12-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 SQL实现 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档