PHP: finding a set of numbers in a database that sums up to a specific number

Question

Firstly, I am new to php ... so I am still code and understand php procedurally. what,

I have a set of numbers (quantity) stored in a database.

Question : using PHP and mySQL,

• What is the best way to retrieve this information from a database so that the amount is related to its transaction ID

• Most importantly, I need to find the corresponding set of numbers in db, which is equal to the sum of 29 .

Below is the Transaction_tlb transaction table for my mydb database

  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 

Now I have an idea ... but it is not effective. I am going to try all possible cases. value, if I have n values ​​to check, the time complexity will be around 2 ^ n. this is very inefficient (plus, I don’t even know if my code makes sense (see below)

I saw a similar example in this YouTube video: https://www.youtube.com/watch?v=XKu_SEDAykw&t

but I don’t know exactly how to write code in php.

The code:

 <?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; } }?> 

Can someone point me in the right direction? this code does not work ... and even if it works ... this method is inefficient at all. What happens when Ive got 3 million records to work with? I need some help, please.

Answer 1

You can state your problem in terms of the 0/1 Knapsack problem . A ready-to-use implementation in PHP is available .

Using the knapSolveFast2 function defined on the linked page, you can continue, as in the example below. The idea here is that you set the “weights” included in the Knapsack algorithm to be equal to the values ​​themselves.

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

which gives:

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

Notes:

• you can modify your SQL query to skip rows with amount greater than the required amount (29)
• the above function will choose one solution (provided that it exists), it will not provide all of them
• you should check whether the return value of $m4 is really equal to the given sum (29) - as the algorithm works, the specified amount is only the upper limit, which is not guaranteed (for example, for 37 instead of 29, the return value is only 34, since there is no combination of input numbers, the sum of which would give 37)

Answer 2

This is really a problem with a backpack, but I will try to give a complete solution that is not optimal, but illustrates a complete strategy for solving your problem.

First of all, you can do this with just one iteration over an array of numbers without recursion and without preliminary sorting. Dynamic programming is all you need, tracking all the previously possible paths of a partial sum. The idea is somewhat similar to your described recursive method, but we can do it iteratively and without pre-configuration.

Assuming the input array [84, 38, 12, 13, 17, 2, 78, 1, 1] and target 29, we scroll the numbers like this:

 * 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. 

The trick is that when we subTargets numbers, we save the subTargets lookup subTargets , which is a number that will give us a solution using one or more combinations ("paths") of the numbers we saw before. If the new number is subTarget, we add to our list of solutions; if not, then add to the existing paths, where num<subTarget and move on.

PHP quick and dirty function for this:

 // 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. Eg 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; } 

Run the code as follows:

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

which outputs:

 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