查找符合远程标准的组合

我有一个包含1000行的零件列表。这两个字段是“部件号”和“成本”。成本范围从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（总计$ 74）
A370，B309，A084，A034（总计$ 74）

我的第一个想法是通过部件的所有可能的组合迭代可能符合条件（即< =范围的上限），并报告总和落在范围内的那些组合。它很快就变得很明显，因为组合的数量变得非常快，天文数字很快就会失败。但鉴于大多数组合不符合标准，这个问题是否可以合理解决？

鉴于数据在MySQL数据库的表中，我的首选解决方案是SQL或Stored Proc，下一个首选PHP，最后是Javascript。

（ETA：由@piotrm发现错过命中）

来源

2012-02-17 biscuit314

你必须限制最大总成本的，或组合的数量将无论你如何找到它们，都要上天。在下面的例子中它被限制为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

来源

2012-02-17 22:31:38 piotrm

我接受了这个答案，因为它与问题中的测试数据一起工作。但是，除非证明它可能无法解决，否则它不能解决我的问题。这基本上是我考虑的第一种方法（遍历所有组合）添加首先将所有组合存储在表中的想法。就像你说的那样，小组的作品会随着名单的增长而变得疯狂。感谢您确认在阶乘墙上没有办法。 – biscuit314 2012-02-18 16:46:38

嗯，我首先想到的是只自连接从那里的成本是低于该范围的高端表中的行：

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

这会是多高效？

很行小于MAX_COST的数目为O（n^2）。如果这个数字不是相对较小，这可能会很慢
它是中的O（n）parts中的行数。如果parts非常大，这可能是决定性因素。但是，如果parts是没有那么大，或者如果（1）不小，这将得到由（1）

来源

2012-02-17 21:12:19

我需要弄清楚如何删除重复的子查询！ – 2012-02-17 21:13:18

我相信sql语法分析器不会启动该查询2次 – dynamic 2012-02-17 21:25:07

如果需求恰好需要满足范围的两个部分，那么干得好。不幸的是，部件数量可能会有所不同 – biscuit314 2012-02-18 16:38:38

我有一个递归（上阵列）淹没：

$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); 
    } 
}

用法应该是显而易见的，但只是为的情况下，假设你要处理$array为间隔<70,90>值;

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

_{我没有测试它，我很好奇它的性能......在评论中留下的笔记，请}

来源

2012-02-17 22:00:06 Vyktor

这不起作用 - 返回的结果与预期不同（许多组合小于下限）。我很欣赏这种努力。 – biscuit314 2012-02-18 17:03:18

查找符合远程标准的组合

回答

相关问题