алгоритм — PHP: поиск набора чисел в базе данных, который суммирует до определенного числа

Во-первых, я новичок в PHP … так что я все еще кодирую и понимаю php процедурно. что сказал,

У меня есть коллекция чисел (сумма), хранящихся в базе данных.

Вопрос: Используя PHP и MySQL,

  1. Каков наилучший способ вывести эту информацию из базы данных так, чтобы сумма была связана с ее идентификатором транзакции?

  2. Самое главное, мне нужно найти соответствующий набор чисел в БД, который равен сумме 29.

Ниже таблица транзакций, Transaction_tlb, для моей базы данных mydb

    Transaction_ID |     Name         |       Date      | Amount
---------------|------------------|-----------------|------------
11012          | Jonathan May     |   6/12/2016     |     84
21012          | John Pedesta     |   6/12/2016     |     38
31012          | Mary Johnson     |   1/01/2017     |     12
41012          | John Johnson     |   8/01/2017     |     13
51012          | Keith Jayron     |   8/01/2017     |     17
61012          | Brenda Goldson   |   8/01/2017     |     2
71012          | Joshua Traveen   |   8/01/2017     |     78
81012          | Remy ma Goldstein|   8/01/2017     |     1
91012          | Barbie Traveen   |   8/01/2017     |     1

Теперь у меня есть идея .. но это не эффективно. Я собираюсь попробовать каждый возможный случай. Это означает, что если у меня есть n значений для проверки, сложность времени будет около 2 ^ n. это крайне неэффективно (плюс, я даже не знаю, имеет ли мой код какой-либо смысл. (увидеть ниже)

Я видел похожий пример в этом видео на YouTube: https://www.youtube.com/watch?v=XKu_SEDAykw&T

но я не уверен, как именно написать код в php.

Код:

<?php
if (!mysql_connect("localhost", "mysql_user", "mysql_password") || !mysql_select_db("mydb")) {
die("Could not connect: " . mysql_error()); } //End DB Connect

$capacity = 29; //Knapsack Capacity or Sum

//Select Transact ID and Value from the Database where Amount is <= Capacity
$fetchQuery = "SELECT 'Transaction_ID', 'Amount' FROM 'Transaction_tlb' WHERE 'Amount' <= $capacity";

$components = array(); //new array to hold components

if ($queryResults = mysql_query($fetchQuery)) {

//check if data was pulled
if (mysql_num_row($queryResults) != NULL) {
while ($row = mysqli_fetch_assoc($queryResults) {
$components[$row['Transaction_ID']] = $row['Amount'];
}
}
}

/* Correct me if i am wrong, but, Components associative array Should be something like
$components = array('11012'=> 84, '21012'=> 38, '31012'=> 12, '41012'=> 13, '51012'=> 17,
'61012'=> 2, '71012'=> 78, '81012'=> 1, '91012'=> 1);
*/

$components = asort($components) // sort array in ascending order
$componentCount = count($component)function match ($componentCount, $capacity) {
$temp = match (($componentCount - 1), $capacity);
$temp1 = $component[$componentCount] + match (($componentCount - 1), ($capacity - $component[$componentCount]));
$result = max($temp, $temp1);
return $result;
}
}?>

Может кто-нибудь, пожалуйста, укажите мне в правильном направлении? этот код не работает … и даже если он работает … метод вообще не эффективен. что происходит, когда у меня есть 3 миллиона записей для работы? Мне нужна помощь, пожалуйста.

6

Решение

Вы можете сформулировать свою проблему с точки зрения 0/1 рюкзак проблема. Готовая реализация в PHP имеется в наличии.

Используя функцию knapSolveFast2 определенный на связанной странице, можно продолжить, как в примере ниже. Идея здесь состоит в том, что вы устанавливаете «веса», вводящие алгоритм ранца, равными самим значениям.

$components = array(84, 38, 12, 13, 17, 2, 78, 1, 1);

$m = array();
list($m4, $pickedItems) = knapSolveFast2($components, $components, sizeof($components)-1, 29, $m);

echo "sum: $m4\n";
echo "selected components:\n";
foreach($pickedItems as $idx){
echo "\t$idx --> $components[$idx]\n";
}

который дает:

sum: 29
selected components:
2 --> 12
4 --> 17

Заметки:

  • Вы можете изменить свой SQL-запрос, чтобы пропустить строки с amount больше необходимой суммы (29)
  • функция выше выберет одно решение (при условии, что оно существует), оно не предоставит все из них
  • нужно проверить, есть ли возвращаемое значение $m4 действительно равно указанной сумме (29) — поскольку алгоритм работает, указанная сумма является только верхним пределом, который не гарантируется для достижения (например, для 37 вместо 29, возвращаемое значение составляет только 34, поскольку нет комбинация входных чисел, сумма которых даст 37)
3

Другие решения

Это действительно ранняя проблема, но я постараюсь дать полное решение, которое не оптимально, но иллюстрирует полную стратегию решения вашей проблемы.

Прежде всего, вы можете сделать это всего за одну итерацию по массиву чисел без рекурсии и предварительной сортировки. Динамическое программирование — это все, что вам нужно, отслеживая все ранее возможные пути с частичной суммой. Идея чем-то похожа на описанный вами рекурсивный метод, но мы можем сделать это многократно и без предварительной сортировки.

Предполагая входной массив [84, 38, 12, 13, 17, 2, 78, 1, 1] и цель 29, мы перебираем числа следующим образом:

* 84 - too big, move on
* 38 - too big, move on
* 12 - gives us a subtarget of 29-12 = 17
subtargets:
17 (paths: 12)
* 13 - gives us a subtarget of 29-13=16
subtargets:
16 (paths: 13)
17 (paths: 12)
* 17 - is a subtarget, fulfilling the '12' path;
and gives us a subtarget of 29-17=12
subtargets:
12 (paths: 17)
16 (paths: 13)
17 (paths: 12)
solutions:
12+17
etc.

Хитрость заключается в том, что при цикле по числам мы храним таблицу поиска subTargets, которые являются числами, которые дали бы нам решение, используя одну или несколько комбинаций («путей») ранее увиденных чисел. Если новый номер является подзадачей, мы добавляем в наш список решений; если нет, то мы добавляем к существующим путям, где num<subTarget и двигаться дальше.

Быстрая и грязная PHP-функция для этого:

// Note: only positive non-zero integer values are supported
// Also, we may return duplicate addend sets where the only difference is the order
function findAddends($components, $target)
{
// A structure to hold our partial result paths
// The integer key is the sub-target and the value is an array of string representations
// of the 'paths' to get to that sub-target. E.g. for target=29
// subTargets = {
//   26: { '=3':true },
//   15: { '=12+2':true, '=13+1':true }
// }
// We are (mis)using associative arrays as HashSets
$subTargets = array();

// And our found solutions, stored as string keys to avoid duplicates (again using associative array as a HashSet)
$solutions = array();

// One loop to Rule Them All
echo 'Looping over the array of values...' . PHP_EOL;
foreach ($components as $num) {
echo 'Processing number ' . $num . '...' . PHP_EOL;

if ($num > $target) {
echo $num . ' is too large, so we skip it' . PHP_EOL;
continue;
}

if ($num == $target) {
echo $num . ' is an exact match. Adding to solutions..' . PHP_EOL;
$solutions['='.$num] = true;
continue;
}

// For every subtarget that is larger than $num we get a new 'sub-subtarget' as well
foreach ($subTargets as $subTarget => $paths) {
if ($num > $subTarget) { continue; }

if ($num == $subTarget) {
echo 'Solution(s) found for ' . $num . ' with previous sub-target. Adding to solutions..' . PHP_EOL;
foreach ($paths as $path => $bool) {
$solutions[$path . '+' . $num] = true;
}
continue;
}

// Our new 'sub-sub-target' is:
$subRemainder = $subTarget-$num;
// Add the new sub-sub-target including the 'path' of addends to get there
if ( ! isset($subTargets[$subRemainder])) { $subTargets[$subRemainder] = array(); }

// For each path to the original sub-target, we add the $num which creates a new path to the subRemainder
foreach ($paths as $path => $bool) {
$subTargets[$subRemainder][$path.'+'.$num] = true;
}
}

// Subtracting the number from our original target gives us a new sub-target
$remainder = $target - $num;

// Add the new sub-target including the 'path' of addends to get there
if ( ! isset($subTargets[$remainder])) { $subTargets[$remainder] = array(); }
$subTargets[$remainder]['='.$num] = true;
}
return $solutions;
}

Запустите код так:

$componentArr = array(84, 38, 12, 13, 17, 2, 78, 1, 1);
$addends = findAddends($componentArr, 29);

echo 'Result:'.PHP_EOL;
foreach ($addends as $addendSet => $bool) {
echo $addendSet . PHP_EOL;
}

какие выводы:

Looping over the array of values...
Processing number 84...
84 is too large, so we skip it
Processing number 38...
38 is too large, so we skip it
Processing number 12...
Processing number 13...
Processing number 17...
Solution(s) found for 17 with previous sub-target. Adding to solutions..
Processing number 2...
Processing number 78...
78 is too large, so we skip it
Processing number 1...
Processing number 1...
Solution(s) found for 1 with previous sub-target. Adding to solutions..

Result:
=12+17
=12+13+2+1+1
1

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector