PHP：在数据库中查找一组总和为特定数字的数字
PHP: Finding a set of numbers in a database that sums up to a particular number
首先，我是一个 php 新手...所以我仍然在程序上编码和理解 php。也就是说，
我有一组数字（数量）存储在数据库中。
问题：使用PHP和mySQL，
从数据库中提取此信息的最佳方法是什么，这样金额将与其交易 ID 相关联
最重要的是，我需要在数据库中找到一组匹配的数字，其总和等于 29。
下面是我的数据库 mydb
的交易 Table , Transaction_tlb
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;
}
}?>
谁能给我指出正确的方向？这段代码不起作用……即使它起作用了……该方法根本没有效率。当我有 300 万条记录可供使用时会发生什么？我需要帮助。
您可以根据 0/1 Knapsack problem. Ready-to-use implementation in PHP is available.
来表述您的问题
使用链接页面中定义的函数knapSolveFast2，可以按照下面的示例进行操作。这里的想法是将进入背包算法的 "weights" 设置为等于值本身。
$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) 的行
- 上面的函数会选择一个解决方案（假设它存在），它不会提供所有的解决方案
- 应该检查 return 值
$m4 是否确实等于指定的总和 (29) - 由于算法有效，指定的金额只是上限，不能保证达到（例如，对于 37 而不是 29，return 值仅为 34，因为没有输入数字的组合，其总和将产生 37）
这确实是一个背包问题，但我会尝试给出一个不是最优的完整解决方案，但会说明解决您的问题的完整策略。
首先，您只需对数字数组进行一次迭代即可完成此操作，无需递归，也无需预排序。动态规划就是您所需要的，跟踪所有以前可能的部分和 'paths'。这个想法有点类似于你描述的递归方法，但我们可以迭代地完成它而不需要预排序。
假设输入数组 [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.
这里的技巧是，在遍历数字时，我们会查找 table subTargets，这些数字可以使用一个或多个组合（'paths') 以前见过的数字。如果一个新数字是一个子目标，我们将添加到我们的解决方案列表中；如果不是，那么我们附加到 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
首先，我是一个 php 新手...所以我仍然在程序上编码和理解 php。也就是说，
我有一组数字（数量）存储在数据库中。
问题：使用PHP和mySQL，
从数据库中提取此信息的最佳方法是什么，这样金额将与其交易 ID 相关联
最重要的是，我需要在数据库中找到一组匹配的数字，其总和等于 29。
下面是我的数据库 mydb
Transaction_tlb
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;
}
}?>
谁能给我指出正确的方向？这段代码不起作用……即使它起作用了……该方法根本没有效率。当我有 300 万条记录可供使用时会发生什么？我需要帮助。
您可以根据 0/1 Knapsack problem. Ready-to-use implementation in PHP is available.
来表述您的问题使用链接页面中定义的函数knapSolveFast2，可以按照下面的示例进行操作。这里的想法是将进入背包算法的 "weights" 设置为等于值本身。
$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) 的行
- 上面的函数会选择一个解决方案（假设它存在），它不会提供所有的解决方案
- 应该检查 return 值
$m4是否确实等于指定的总和 (29) - 由于算法有效，指定的金额只是上限，不能保证达到（例如，对于 37 而不是 29，return 值仅为 34，因为没有输入数字的组合，其总和将产生 37）
这确实是一个背包问题，但我会尝试给出一个不是最优的完整解决方案，但会说明解决您的问题的完整策略。
首先，您只需对数字数组进行一次迭代即可完成此操作，无需递归，也无需预排序。动态规划就是您所需要的，跟踪所有以前可能的部分和 'paths'。这个想法有点类似于你描述的递归方法，但我们可以迭代地完成它而不需要预排序。
假设输入数组 [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.
这里的技巧是，在遍历数字时，我们会查找 table subTargets，这些数字可以使用一个或多个组合（'paths') 以前见过的数字。如果一个新数字是一个子目标，我们将添加到我们的解决方案列表中；如果不是，那么我们附加到 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