Найти комбинации, соответствующие критериям дальности

Вы должны ограничить максимальную общую стоимость, или количество комбинаций будет повышаться до неба независимо от того, как вы пытаетесь их найти. В следующем примере оно ограничено 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. это O (n ^ 2) в количестве строк меньше MAX_COST . Это может быть медленным, если это число не является относительно небольшим
2. это O (n) в количестве строк по parts . Если parts очень большие, это может быть определяющим фактором. Но если parts не такие большие, или если (1) не мало, это будет зависеть от (1)

У меня есть рекурсивный (по массиву):

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

Нам нужно arsort() отсортировать данные с помощью 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); 

_{Я не тестировал его, и мне интересно, как это работает … Оставлять комментарии в комментариях}