选择30个随机行,其中sum amount = x

Question

我有一张桌子

items
id int unsigned auto_increment primary key,
name varchar(255)
price DECIMAL(6,2)

我希望从这张表中获得至少30个随机商品,其中总价格等于500,实现这一目标的最佳方法是什么？

我已经看到这个看起来有类似问题的解决方案MySQL选择3个随机行,其中三行的总和小于值

我想知道是否有任何其他解决方案更容易实现和/或更高效

Answer 1

我能提供的最接近的答案就是这个

set @cnt = 0;
set @cursum = 0;
set @cntchanged = 0;
set @uqid = 1;
set @maxsumid = 1;
set @maxsum = 0;
select 
    t.id,
    t.name,
    t.cnt
from (
    select 
        id + 0 * if(@cnt = 30, (if(@cursum > @maxsum, (@maxsum := @cursum) + (@maxsumid := @uqid), 0)) + (@cnt := 0) + (@cursum := 0) + (@uqid := @uqid + 1), 0) id, 
        name,  
        @uqid uniq_id,
        @cursum := if(@cursum + price <= 500, @cursum + price + 0 * (@cntchanged := 1) + 0 * (@cnt := @cnt + 1), @cursum + 0 * (@cntchanged := 0)) as cursum, if(@cntchanged, @cnt, 0) as cnt  
    from (select id, name, price from items order by rand() limit 10000) as orig
) as t

where t.cnt > 0 and t.uniq_id = @maxsumid
;

它是如何工作的？首先,我们从项目中选择10k随机排序的行.在它之后我们总结物品的价格,直到我们达到30项,总和少于500.当我们找到30项时,我们重复这个过程,直到我们遍历所有10k选定的项目.在找到这30个项目时,我们可以节省最多的总和.因此,最后我们选择30个具有最大总和的项目(意味着最接近目标500).不确定这是否是你最初想要的,但找到500 的确切总和将需要在DB方面付出太多努力.

Answer 2

如果您的产品列表满足以下假设，就有一个解决方案：

您拥有所有价格在 0.00 到 500.00 之间的产品。例如。0.01、0.02 等至 499.99。或者可能是 0.05、0.10 等到 499.95。

该算法基于以下内容：

在总和为 S 的 n 个正数的集合中，至少有一个小于 S 除以 n (S/n)

在这种情况下，步骤是：

1. 随机选择价格 < 500/30 的产品。获取它的价格，比如说 X。
2. 随机选择价格 < (500 - X)/29 的产品。获取其价格，假设为 Y。
3. 随机选择价格 < (500 - X - Y)/28 的产品。

重复29次，得到29种产品。对于最后一个产品，选择价格 = 剩余价格 的产品。（或价格 <= 剩余价格并按价格降序排序，希望您能足够接近）。

对于表项：

获取随机产品最高价格：

CREATE PROCEDURE getRandomProduct (IN maxPrice INT, OUT productId INT, productPrice DECIMAL(8,2))
BEGIN
   DECLARE productId INT;
   SET productId = 0;
       SELECT id, price INTO productId, productPrice
       FROM items
       WHERE price < maxPrice
       ORDER BY RAND()
       LIMIT 1;
END

获得29个随机产品：

CREATE PROCEDURE get29products(OUT str, OUT remainingPrice DECIMAL(8,2))
BEGIN
  DECLARE x INT;
  DECLARE id INT;
  DECLARE price DECIMAL(8,2);
  SET x = 30;
  SET str = '';
  SET remainingPrice = 500.00;

  REPEAT
    CALL getRandomProduct(remainingPrice/x, @id, @price);
    SET str = CONCAT(str,',', @id);
    SET x = x - 1;
    SET remainingPrice = remainingPrice - @price;
    UNTIL x <= 1
  END REPEAT;
END

调用程序：

CALL `get29products`(@p0, @p1); SELECT @p0 AS `str`, @p1 AS `remainingPrice`;

最后尝试找到最后一个达到 500 的产品。

或者，您可以选择 28 并使用您提供的链接问题的解决方案来获得几个产品，其总和等于剩余价格。

请注意，允许重复产品。为了避免重复，您可以getRandomProduct使用已找到的产品的附加 IN 参数进行扩展，并添加条件NOT IN以排除它们。

更新：您可以克服上述限制，以便您始终通过使用 cron 进程找到总和为 500 的集合，如下面第二部分所述。

第二部分：使用 cron 进程

根据@Michael Zukowski 的建议，你可以

• 创建一个表来保存找到的集合
• 定义一个 cron 进程，多次运行上述算法（在示例中为 10 次），例如：每 5 分钟
• 如果找到与总和匹配的集合，则将其添加到新表中

通过这种方式，您可以找到总和始终恰好为 500 的集合。当用户发出请求时，您可以从新表中选择随机集合。

即使匹配率为 20%，如果 cron 进程在 24 小时内每 5 分钟运行该算法 10 次，您也可以收集超过 500 个集合。

我认为使用 cron 进程有以下优点和缺点：

优点

• 找到精确匹配
• 没有根据客户要求进行处理
• 即使匹配率低，您也可以找到多个集合

缺点

• 如果价格数据频繁更新，您可能会得到不一致的结果，也许使用 cron 进程不起作用。
• 必须丢弃或过滤旧的集合
• 每个客户端可能不是随机的，因为不同的客户端可能会看到相同的集合。