查找符合范围标准的组合

Find combinations that meet a ranged criteria

本文关键字：组合 标准 范围 查找      更新时间：2023-09-26

我有一个包含1000行的零件列表。这两个字段是"零件号"answers"成本"。费用从1美元到2000美元不等（全部为整数）。

  • A034，1
  • A012，5
  • A084，10
  • B309，13
  • A094，25
  • A370，50
  • A233，75
  • A343，75
  • C124，78
  • d239000
  • x9981980
  • z9012000

我想创建一个所有零件组合的列表，这些零件的组合成本在一个严格的范围内（范围的差距永远不会超过50美元）。例如，给定70-75美元的范围，返回的列表将是：

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

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

假设数据在MySQL数据库的表中，我的首选解决方案是一些SQL或StoredProc，其次是PHP，最后是Javascript。

（ETA：@piotrm发现的未命中）

您必须限制总成本的最大值，否则无论您如何找到组合，组合的数量都会飙升。在下面的示例中，它被限制为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

好吧，我的第一个想法是只自连接表中成本低于高端范围的行：

select 
  l.part as `part1`, r.part as `part2`, l.cost + r.cost as `total cost`
from (select * from parts where cost < MAX_COST) l
inner join
(select * from parts where cost < MAX_COST) r
on l.cost + r.cost between MIN_COST and MAX_COST

这将有多高效

  1. 在小于CCD_ 1的行数中为O（n^2）。如果这个数字不是相对较小的话，这可能会很慢
  2. 它是CCD_ 2中行数中的O（n）。如果parts非常大，这可能是决定因素。但如果parts不那么大，或者（1）不小，这将被（1）淹没

我有一个递归（在数组上）：

$data = array( 
  'A034' => 1,
  'A012' => 5,
  'A084' => 10,
  ...
)

我们需要先用值最高的arsort()对数据进行排序：

arsort( $data, SORT_NUMERIC);

这将确保数组的大部分将在早期阶段得到处理。关于主要功能：

/**
 * Builds resulting array
 *
 * @param $array $key => $price pairs
 * @param $price lower price of interval (for <70,130>, it's 70)
 * @param $reserve difference between lower and higher price (for <70,130>, it's 130-70 = 59)
 * @param &$result output array
 * @param $cummulatedKeys so far collected keys, leave empty
 *
 * @return void
 */
function buildResults( $array, $price, $reserve, &$result, $cumulatedKeys = array()){
    // Get key of first element
    reset( $array);
    $key = key( $array);
    // Just decrease number of elements as fast as possible
    while( $one = array_shift( $array)){
       $tmp = $price - $one;
       // Ok reached one price
       if( $tmp >= 0){
           // In interval
           if( (-$tmp) <= $reserve){
               $result[] = array_merge( $cumulatedKeys, array( $key));
           } else {
                 // We are too low
                 continue;
           }
       }
       // Skip very small values which can't accumulate price
       if( (count( $array) * $one) < $tmp){
           break;
       }
       // We may go on, deeper
       buildResults( $array, $tmp, $reserve, $result, array_merge( $cumulatedKeys, array( $key)));
       // Actualize key
       if( !count( $array)){
           break;
       }
       reset( $array);
       $key = key( $array);
   }
}

用法应该是显而易见的，但仅针对这种情况，假设您希望为值间隔<70,90>处理$array；

$result = array();
buildResults( $array, 70, 90-70, $result);

我还没有测试过它，我对它的性能很好奇。。。请在评论中留下注释

相关文章：