查找符合一定范围条件的组合 [英] Find combinations that meet a ranged criteria
问题描述
我有一个1000行的零件清单.这两个字段是零件号"和成本".费用从1美元到2000美元不等(全部).
I have a parts list with 1000 rows. The two fields are "Part Number" and "Cost". The costs range from $1 to $2000 (integers all).
- A034，1
- A012，5
- A084，10
- B309，13
- A094，25
- A370，50
- A233、75
- A343，75
- C124，78
- ...
- D239，500
- ...
- X998，1980
- Z901，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，返回的列表将是:
I want to create a list of all combinations of parts whose combined cost falls within a tight range (the gap of the range will never be more than $50). For example, given a range of $70-75, the returned list would be:
- A343(总计75美元)
- A233(总计75美元)
- A370，A094(总计75美元)
- A370，B309，A084(总计73美元)
- A370，B309，A084，A034(总计74美元)
我的第一个想法是遍历所有可能满足标准的部件组合(即<==范围的上限)，并报告那些总和在范围内的组合.很快就发现失败了，因为组合的数量很快就变成了天文数字.但是，考虑到大多数组合都不符合标准，这个问题是否可以合理解决?
My first thoughts were to iterate through all possible combinations of parts that could meet the criteria (i.e. <= the upper number of the range) and report those combinations whose sums fell within the range. It quickly became obvious that would fail because the number of combinations becomes astronomical pretty quickly. But given that most combinations would not meet the criteria, is this problem reasonably solvable?
鉴于数据位于MySQL数据库的表中，我的首选解决方案是使用SQL或Stored Proc，然后是首选的PHP，最后是Javascript.
Given that the data is in a table in a MySQL database, my preferred solution would be some SQL or Stored Proc, next preferred PHP, finally Javascript.
(ETA:@piotrm发现的未命中歌曲)
(ETA: the missed hit discovered by @piotrm)
推荐答案
您必须限制总费用的最高限额，否则无论您如何找到它们，组合的数量都会飞涨.在下面的示例中，该值限制为75，但是您可以尝试其他值以查看它，您仍然可以在合理的时间内找到结果.
You have to limit maximum of total cost, or the number of combinations will go up to the sky no matter how you try to find them. In the following example it is limited to 75, but you may try other values to see it you can still find results in a reasonable time.
您还可以调整此解决方案，以更新插入表上的组合表或更新主表，从而在不超过设置限制的任何范围内获得极快的结果(但是明显会减慢插入速度，因为所有工作已完成) ).
You can also adapt this solution to update combinations table on inserts or updates for your main table, letting you get results extremely quick for any range that doesnt exceed your set limit (but slowing inserts obviously as it's where all the work is done).
创建表并触发:
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);
最后使用以下方法获得结果:
And finally get your result using:
SELECT * FROM total_max75 WHERE total BETWEEN 70 AND 75;
您可以在此处放置最大不超过75的任何范围(或在表创建部分和触发器中设置为限制的任何范围).
You may put any range here with maximum less than 75 (or whatever you set as limit in the table creation part and trigger).
结果:
A084, A370, B309 73 (you missed this one in your question)
A034, A084, A370, B309 74
A233 75
A343 75
A094, A370 75
这篇关于查找符合一定范围条件的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
