2

我有一个数组

$array = array(3,5,6,10,15,30);
$sum = 69;

那么有 3 个不同的和等于 69：

3+5+6+10+15+30,
3+6+10+20+30,
3+6+30+30,

最好的是3+6+30+30。因为它包含来自数组的更高数字来完成减少数字计数的总和。

（一个数字可以在总和中使用的次数与它在列表中出现的次数一样多，并且单个数字计为总和。）这是我正在实现的代码

$sum = 18;
$list = array();
$this->sumUpRecursive(array(3,5,6,10,15,30), $list);  //function call
$list = array_filter($list,function($var) use ($sum) { return(array_sum($var) == $sum);});
var_dump($list);

function sumUpRecursive($array, &$list, $temp = array()) {
      if (count($temp) > 0 && !in_array($temp, $list))
        $list[] = $temp;
      for ($i = 0; $i < sizeof($array); $i++) {
        $copy = $array;
        $elem = array_splice($copy, $i, 1);
        if (sizeof($copy) > 0) {
          $add = array_merge($temp, array($elem[0]));
          sort($add);
          $this->sumUpRecursive($copy, $list, $add);
        }
        else {
          $add = array_merge($temp, array($elem[0]));
          sort($add);
          if (!in_array($temp, $list)) {
            $list[] = $add;
          }
        }
      }
    }

结果：

Array
    (
[9] => Array
    (
        [0] => 3
        [1] => 5
        [2] => 10
    )

[28] => Array
    (
        [0] => 3
        [1] => 15
    )

)

我希望这可能有点复杂。它从数组中取一个数字一次。但是如何计算出69...

谢谢

4

1 回答 1

1

这应该适合你：

这段代码有什么作用（函数getKnapsackSum()）？

1.准备数据

在函数的前几行中，我准备了数据，这意味着我对数组 DESC 进行了排序rsort()。我用 获取列表的最后一个元素，用end()重置数组指针rest()并将其分配给临时变量。

2.输入检查

在我开始计算总和之前，我检查输入是否不是 0。

3.计算总和

在这之后，真正的事情发生了（IT 巫术，不是真的）！只要我没有得到总和，我就会从一个错误的循环开始。while 循环中的下两行用于检查，首先如果无法计算总和，它返回一个带有 0 的数组，其次是当我们得到数组指针的“偏移量”时，我设置它返回最后一个数组元素。

然后第一个 if 子句用于检查它是否犯了错误，它必须用较低的值进行尝试。举个例子：

list = [3, 5, 6]
sum = 8


                        //entire sum
                        | 0
                        |
check 6:                |
                        |
      6 + sum  -> 8     | 6               | fits
      6 + sum  -> 8     |                 | does not fit
                        |
check 5:                |
                        |
      5 + sum  -> 8     |                 | does not fit
                        |
check 3:                |
                        |
      3 + sum  -> 8     |                 | does not fit

--------------------------------------------------------
                          = sum = [6] != 8

正如你在这个例子中看到的那样，算法犯了一个错误，因为它开始用 6 构建总和，但是在此之后它直到最后都无法构建它，现在这里是第一个 if 子句检查的地方，如果数组指针的当前元素是数组的末尾，并且这个值 + 当前总和高于目标。

如果是这种情况，它会从 sum 数组中删除最后一个值并弹出列表的最高元素。因此，现在它使用以下数据再次尝试：

list = [3, 5]
          //^ As you can see it removed the highest value of the list 
sum = 8


                        //entire sum
                        | 0 <- it removed the last value of the sum array, here 6
                        |
check 5:                |
                        |
      5 + sum  -> 8     | 5               | fits
      5 + sum  -> 8     |                 | does not fit
                        |
check 3:                |
                        |
      3 + sum  -> 8     | 3               | fits
      3 + sum  -> 8     |                 | does not fit

--------------------------------------------------------
                          = sum = [5, 3] == 8

因此，正如您现在所看到的，第一个 if 子句使使用列表构建总和成为可能。所以 if 语句确保它纠正了级别 1 的错误。

现在，我的 while 循环中的第二个 if 语句更正了级别 2 的错误。那么级别 2 的错误是什么？我们也再看一个例子：

list = [3, 5, 6]
sum = 22


                        //entire sum
                        | 0
                        |
check 6:                |
                        |
      6 + sum  -> 22    | 6               | fits
      6 + sum  -> 22    | 6               | fits
      6 + sum  -> 22    | 6               | fits
      6 + sum  -> 22    |                 | does not fit
                        |
check 5:                |
                        |
      5 + sum  -> 22    |                 | does not fit
                        |
check 3:                |
                        |
      3 + sum  -> 22    | 3               | fits
      3 + sum  -> 22    |                 | does not fit

--------------------------------------------------------
                          = sum = [6, 6, 6, 3] != 22

所以你可以看到它不能完全建立总和。但是这次它不是级别 1 的错误，因为如果我们从当前总和中取出最后一个元素并遍历我们删除最高元素的新列表，它仍然无法构建总和，如您在此处看到的：

更正错误级别 1：

list = [3, 5]
          //^ As you can see it removed the highest value of the list 
sum = 22


                        //entire sum
                        | [6, 6, 6] <- it removed the last value of the sum array, here 3
                        |
check 5:                |
                        |
      5 + sum  -> 22    |                | does not fit
                        |
check 3:                |
                        |
      3 + sum  -> 22    | 3              | fits
      3 + sum  -> 22    |                | does not fit
                        |
--------------------------------------------------------
                          = sum = [6, 6, 6, 3] != 22

所以你可以看到它现在被卡住了，它不能只用第一个 if 子句来纠正错误。这是第二个 if 语句检查列表是否为空的地方，如果是这种情况，则意味着您尝试了每个值，但错误在 sum 数组中更高。

所以现在它返回 sum 数组的 1 个数组元素并将其删除。它还将错误作为偏移量来获得一个没有错误数字的列表。所以在这里：[6, 6, 6, 3]3 从第一个 if 子句中删除，所以现在数组看起来像这样：[6, 6, 6]。现在第二个 if 语句看到错误是 6。它删除它并更正它从中选择数字的列表。

所以现在结果数组看起来像：[6, 6]和从中选择数字的列表是这样的：[5, 3]。现在它对 2 级进行了更正，它可以建立总和，如下所示：

list = [3, 5]
          //^ As you can see it removed the highest value of the list 
sum = 22


                        //entire sum
                        | [6, 6] <- it removed the last value of the sum array, here 3 and 6
                        |
check 5:                |
                        |
      5 + sum  -> 22    | 5              | fits
      5 + sum  -> 22    | 5              | fits
      5 + sum  -> 22    |                | does not fit
                        |
check 3:                |
                        |
      3 + sum  -> 22    |                | does not fit
                        |
                        |
--------------------------------------------------------
                          = sum = [6, 6, 5, 5] == 22

因此，在此之后，if else 语句只是为了检查列表的当前值是否适合 sum 数组并且不大于目标。如果合适，则将其添加到数组中，否则将转到下一个列表元素。


现在你可以看到我的代码纠正了一些错误，但我不能 100% 确定它适用于所有事情，我也不确定你是否会产生 3 级错误，你必须返回 sum 数组一个正确的 3 个值，如果有一个值，我也不确定我的代码是否纠正了它，甚至可能陷入无限循环。

但毕竟这里的谈话是发挥所有魔力的代码：

<?php

    //data
    $arr = [3,5,6,10,15,30];
    $sum = 69;


    //get sum
    function getKnapsackSum($arr, $sum) {
        //prepare data
        rsort($arr);
        $end = end($arr);
        reset($arr);
        $tmp = $arr;
        $result = [];

        //check if it is not a empty input
        if($sum == 0 || empty($tmp) || array_sum($tmp) == 0) return [0];

        //calculate the sum
        while(array_sum($result) != $sum) {
            if(empty($tmp) && empty($result)) return [0];
            if(current($tmp) === FALSE) end($tmp);

            //correction for errors level 1
            if(current($tmp) == $end && array_sum($result) + current($tmp) > $sum) {
                array_pop($result);
                array_shift($tmp);
                reset($tmp);
            }

            //correction for errors level 2
            if(empty($tmp)) {
                $mistake = array_pop($result);
                if($mistake == NULL) return [0];
                $tmp = array_slice($arr, array_search($mistake, $arr)+1);
                reset($tmp);
            }

            if(array_sum($result) + current($tmp) <= $sum)
                $result[] = current($tmp);
            else
                next($tmp);     
        }
        return $result;
    }


    $result = getKnapsackSum($arr, $sum);
    print_r($result);

?>

输出：

Array ( [0] => 30 [1] => 30 [2] => 6 [3] => 3 )

这里还有一些输入示例和我的代码的输出：

    input        |        output    
------------------------------------
 list: []        |
 goal:  0        |  sum: [0]
------------------------------------
 list: []        |
 goal:  1        |  sum: [0]
------------------------------------
 list: [0]       |
 goal:  1        |  sum: [0]
------------------------------------
 list: [0]       |
 goal:  0        |  sum: [0]
------------------------------------
 list: [3, 5, 6] |  //error level 1
 goal:  8        |  sum: [5, 3]
------------------------------------
 list: [3, 5, 6] |  //error level 2
 goal: 22        |  sum: [6, 6, 5, 5]
------------------------------------
 list: [5, 7, 9] |  //can't build the sum
 goal: 56        |  sum: [0]
------------------------------------
 list: [5, 7, 9] |
 goal: 34        |  sum: [9, 9, 9, 7]
------------------------------------
于 2015-03-05T05:17:55.770 回答