选择30个随机行，其中总和= x

Question

我有桌子

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

我希望从此表中至少获得30个随机物品，其中总价格等于500，那么实现此目的的最佳方法是什么？

我看过了这个解决方案，它看起来也有类似的问题。MySQL选择3个随机行，其中三行之和小于值

我想知道是否还有其他更易于实施和/或更有效的解决方案

Answer 1

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

您有所有价格在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的建议为基础，您可以

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

这样，您可以找到 总精确等于500的 集合。当用户发出请求时，您可以从新表中选择一个随机集合。

即使匹配率达到20％，一个cron进程也会在24小时内每5分钟运行该算法10次，您可以收集500多个集合。

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

优点

• 查找完全匹配
• 客户未要求处理
• 即使匹配率较低，您也可以找到多个收藏集

缺点

• 如果价格数据经常更新，您可能会得出不一致的结果，也许使用cron流程将行不通。
• 必须丢弃或过滤旧收藏
• 每个客户端可能不会是随机的，因为不同的客户端可能会看到相同的集合。