专栏首页SQL实现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  

本文分享自微信公众号 - SQL实现(gh_684ee9235a26),作者:zero

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 背包问题

    问题描述 假设你是一个贪婪的小偷,背着可以装35磅重东西的背包,在商场伺机偷窃各种可以装入背包的商品。 ? 你力图往背包中装入价值最高的商品,你会用哪种算法呢?...

    我没有三颗心脏
  • 【动态规划/背包问题】树形背包问题

    从状态定义我们发现,常规的分组背包问题对物品组的考虑是“线性“的(从前往后考虑每个物品组)。

    宫水三叶的刷题日记
  • 【动态规划/背包问题】多维背包问题

    由于每个字符串只能被选一次,且每个字符串的选与否对应了「价值」和「成本」,求解的问题也是「最大价值」是多少。

    宫水三叶的刷题日记
  • 【动态规划/背包问题】分组背包问题

    但对于「组内」物品而言,由于最多只能选一件物品,因此对于成本相同的多件物品,我们应当只保留价值最大的物品,从而让总的物品数量变少。

    宫水三叶的刷题日记
  • 【leetcode】背包问题

    完全背包的特点恰是每种物品可选无限件,所以就可以并且必须采用 w = W[i]…carry 的顺序循环:

    JNingWei
  • 【动态规划/背包问题】背包问题第一阶段最终章:混合背包问题

    但其实「多重背包」并没有这么常见,以至于在 LeetCode 上我都没找到与「多重背包」相关的题目。

    宫水三叶的刷题日记
  • 初识背包问题之 「 0-1 背包 」

    背包问题可以说是一个老生常谈的问题,通常被用作面试题来考查面试者对动归的理解,我们经常说学算法,初学者最难理解的就是 “二归”,一个叫递归,另一个叫动归。

    五分钟学算法
  • 动态规划-背包问题(01背包、完全背包、多重背包)

    背包问题:有多个重量不同、价值不同的物品,以及一个容量有限的背包,选择一些物品装入背包,求最大总价值。 背包问题无法用贪心求最优解,是典型的动态规划...

    唔仄lo咚锵
  • <dp> 0--1背包问题

    有n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

    大学里的混子
  • 0-1背包问题

    问题描述: 0-1背包问题:给定n种物品和一背包。物品 i 的重量似乎 wi,其价值为 vi,背包的容量为 c。问应该如何选择装入背包中的物品,使得装入背包中物...

    我没有三颗心脏
  • 0-1背包问题

  • 完全背包问题

    种花家的奋斗兔
  • 01背包问题(二)

    01背包的时间复杂度很难再降低了,但空间复杂度还能进行优化,可以把数组从二维降到一维。

    无道
  • 01背包问题(一)

    链接:https://www.acwing.com/problem/content/2/

    无道
  • 《0-1 背包问题》

        第一,包的容量比该商品体积小,装不下,此时的价值与前i-1个的价值是一样的,即V(i,j)=V(i-1,j);

    梅花
  • 二维背包问题

    顾名思义,对于某种物品分别有两种代价,假设第i件商品的两种代价分别为为a[i], b[i],一个背包对于a, b两种花费固有的容量记做V, U。

    你的益达
  • 【动态规划/背包问题】树形背包问题练习篇

    今天将练习「树形背包」问题,今天的练习题是一道学习「树形背包/有依赖的背包」问题必做的入门题。

    宫水三叶的刷题日记
  • 【动态规划/背包问题】分组背包问题练习篇

    由于 LeetCode 没有与「分组背包求最大价值」相关的题目,因此我们使用「分组背包求方案数」来作为练习篇。

    宫水三叶的刷题日记
  • 【动态规划/背包问题】详解「完全背包」问题 & 三种背包问题之间的内在关系

    其实就是在 0-1 背包问题的基础上,增加了每件物品可以选择「有限次数」的特点(在容量允许的情况下)。

    宫水三叶的刷题日记

扫码关注云+社区

领取腾讯云代金券