php - 查找满足范围条件的组合

Question

我有一个包含 1000 行的零件 list 。这两个字段是“部件号”和“成本”。成本从 1 美元到 2000 美元不等(全部为整数)。

• A034, 1
• A012, 5
• A084, 10
• B309, 13
• A094, 25
• A370, 50
• A233, 75
• A343, 75
• C124, 78
• ...
• D239, 500
• ...
• X998, 1980
• Z901, 2000

我想创建一个所有部件组合的列表，这些部件的组合成本在一个很小的范围内(范围的差距永远不会超过 50 美元)。例如，给定 70-75 美元的范围，返回的列表将是:

• A343(总计 75 美元)
• A233(总计 75 美元)
• A370、A094(总计 75 美元)
• A370、B309、A084(总计 73 美元)
• A370、B309、A084、A034(总计 74 美元)

我的第一个想法是遍历满足条件(即 <= 范围上限)的所有可能的部分组合，并报告总和在范围内的那些组合。很快就很明显会失败，因为组合的数量很快就会变成天文数字。但考虑到大多数组合都不符合标准，这个问题是否可以合理解决？

鉴于数据位于 MySQL 数据库的表中，我的首选解决方案是一些 SQL 或存储过程，其次是 PHP，最后是 Javascript。

(预计到达时间:@piotrm 发现的未命中)

Answer 1

你必须限制总成本的最大值，否则无论你如何尝试找到它们，组合的数量都会上升到天空。在下面的示例中，它被限制为 75，但您可以尝试其他值以查看它，您仍然可以在合理的时间内找到结果。

您还可以调整此解决方案以更新主表的插入或更新组合表，让您在不超过设置限制的任何范围内非常快速地获得结果(但显然会减慢插入速度，因为所有工作都已完成).

创建表和触发器:

CREATE TABLE `total_max75` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `parts` varchar(255) NOT NULL,
 `num` int(11) NOT NULL,
 `total` int(11) NOT NULL,
 PRIMARY KEY (`id`),
 KEY `total` (`total`,`num`)
); 

CREATE TABLE `newparts` (
 `name` char(4) NOT NULL,
 `price` int(11) NOT NULL,
 PRIMARY KEY (`name`)
);

DELIMITER //
CREATE TRIGGER addtotal AFTER INSERT ON newparts
FOR EACH ROW
BEGIN
IF NEW.price <= 75 THEN
   INSERT INTO total_max75 ( parts, num, total )
     SELECT CONCAT( t.parts, ', ', NEW.name), 
       t.num+1, t.total+NEW.price 
   FROM total_max75 t
   WHERE t.total <= 75 - NEW.price AND num < 40;

   INSERT INTO total_max75( parts, num, total )
     VALUES( NEW.name, 1, NEW.price );
END IF;
END//
DELIMITER ;

然后填充使用:

INSERT INTO newparts( name, price )
SELECT part_number, cost FROM yourtable
WHERE cost <= 75;

或(作为测试数据)

INSERT INTO newparts( name, price ) VALUES
('A012', 5),('A034', 1),('A084', 10),('A094', 25),('A233', 75),
('A343', 75),('A370', 50),('B309', 13),('C124', 78);

最后使用以下方法得到结果:

SELECT * FROM total_max75 WHERE total BETWEEN 70 AND 75;

您可以在此处放置任何最大值小于 75 的范围(或您在表创建部分和触发器中设置的任何限制)。

结果:

A084, A370, B309        73 (you missed this one in your question)
A034, A084, A370, B309  74
A233                    75
A343                    75
A094, A370              75