从 mysql table 中的单个列中找到等于给定总和的数字组合

Question

我有一个 MySQL table 包，其中包含字段 id, max_post。 max_post 中的值包含

  1,2,3,4,5,10,20,30,40,50,100,200,500,1000,2000

我想找到最合适的包裹。比如我输入230，那么应该删除所有内容和 select 200 和 30 个包。我想使用 SQL 查询获得结果。

Answer 1

这是一个装箱问题的例子。基本上，解决它的唯一方法是显式。

您可以通过显式连接获取所有此类组合的列表：

select p1.max_post, p2.max_post, p3.max_post, p4.max_post
from packages p1 left join
     packages p2
     on p1.max_post > p2.max_post left join
     packages p3
     on p2.max_post > p3.max_post left join
     packages p4
     on p3.max_post > p4.max_post
where (p1.max_post + coalesce(p2.max_post, 0) + coalesce(p3.max_post, 0) +
       coalesce(p4.max_post, 0)
      ) = 230
order by (p2.max_post is null) desc,
         (p3.max_post is null) desc,
         (p4.max_post is null) desc

order by 将 "shorter" 列表放在第一位。如果你愿意，你可以添加一个limit。

注意：这实际上是在 table 中的值之间创建四次笛卡尔积。随着 tables 大小的增长，执行时间也会增长。

Answer 2

满足您要求的替代方案 483 => 200,100,50,40

SELECT
    target.max_post,
    p1.id,
    p1.max_post,
    p2.id,
    p2.max_post,
    p3.id,
    p3.max_post,
    p4.id,
    p4.max_post
FROM
(
    SELECT 483 AS max_post
)
    target
LEFT JOIN
    packages p1
        ON  p1.id = (SELECT id
                       FROM packages
                      WHERE max_post <= target.max_post
                   ORDER BY max_post DESC
                      LIMIT 1
                    )
LEFT JOIN
    packages p2
        ON  p2.id = (SELECT id
                       FROM packages
                      WHERE max_post <= target.max_post - p1.max_post
                   ORDER BY max_post DESC
                      LIMIT 1
                    )
LEFT JOIN
    packages p3
        ON  p3.id = (SELECT id
                       FROM packages
                      WHERE max_post <= target.max_post - p1.max_post - p2.max_post
                   ORDER BY max_post DESC
                      LIMIT 1
                    )
LEFT JOIN
    packages p4
        ON  p4.id = (SELECT id
                       FROM packages
                      WHERE max_post <= target.max_post - p1.max_post - p2.max_post - p3.max_post
                   ORDER BY max_post DESC
                      LIMIT 1
                    )

它使用重复的相关子查询。对于非常小的 packages tables，笛卡尔积搜索可能更快 （尽管没有解决上述情况） ，对于任何合理大小的任何东西，我希望相关的子查询更快。

对于 table 的 10 个值
- 笛卡尔积搜索数百种组合 （远远超过 10 choose 4 = 210）
- 相关子查询搜索 40 个值 (10x4)

对于 table 的 100 个值
- 笛卡尔积搜索了数百万种组合 （远远超过 100 choose 4 = 3,921,225）
- 相关子查询搜索 400 个值 (100x4)

Answer 3

这是 Gordon 查询的更正版本。主要是 Gordon 的查询缺少在可用值较小时加入空记录。它为 230 找到的最佳匹配是 200-20-5-4，因为最佳解决方案 200-30-null-null 甚至不在我们正在评估的集合中。这是因为 p3 实际上从未外连接到 200-30，因为 table 中存在值小于 30 的记录。（外连接意味着当有没有匹配时添加一个空记录。）

select 
  p1.max_post, p2.max_post, p3.max_post, p4.max_post
from packages p1 
left join (select max_post from packages union all select null) p2
  on (p1.max_post > p2.max_post or p2.max_post is null)  
left join (select max_post from packages union all select null) p3 
  on (p2.max_post > p3.max_post or p3.max_post is null)  
left join (select max_post from packages union all select null) p4 
  on (p3.max_post > p4.max_post or p4.max_post is null)  
where p1.max_post + coalesce(p2.max_post, 0) + coalesce(p3.max_post, 0) + coalesce(p4.max_post, 0) <= 230
order by 
  p1.max_post + coalesce(p2.max_post, 0) + coalesce(p3.max_post, 0) + coalesce(p4.max_post, 0) desc,
  (p2.max_post is null) desc,
  (p3.max_post is null) desc,
  (p4.max_post is null) desc
limit 1;

（这可以通过在查询中添加 where max_post <= 230 来稍微优化，因此值本身已经高于所需总和的记录将立即被忽略。）

SQL fiddle: http://sqlfiddle.com/#!9/5f6d25/18.

从 mysql table 中的单个列中找到等于给定总和的数字组合

find a combination of numbers that equal a given sum from a single column in mysql table

php

mysql

sql

codeigniter

phpmyadmin