PHP:在数据库中查找一组总和为特定数字的数字

Question

首先，我是一个 php 新手...所以我仍然按程序编写和理解 php。也就是说，

我在数据库中存储了一组数字(数量)。

问题:使用 PHP 和 mySQL，

1. 从数据库中提取此信息的最佳方法是什么，以便金额与其交易 ID 相关联

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

谁能给我指出正确的方向？这段代码不起作用……即使它起作用了……该方法根本没有效率。当我有 300 万条记录可供使用时会发生什么？我需要帮助。

Answer 1

您可以根据 0/1 Knapsack problem 来表述您的问题. PHP 中的即用型实现是 available .

使用链接页面中定义的函数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)