主页 / 问题 / 644023
Accepted
pynista
Asked:2020-03-25 21:01:33 +0000 UTC2020-03-25 21:01:33 +0000 UTC

背包问题：如何从一个数组中选择三个元素，使得它们的和不超过6，同时兼顾数组元素的顺序

  • 772

假设我们有一个数字数组，如下所示：

(2, 1, 4, 1, 3, 5, 6, 1, 2, 6, 3)

帮助我编写一个函数，它将以满足以下条件的方式选择输入数组的 3 个（或更少）元素）：

  1. 结果组的元素之和（例如，以数组的形式）不应超过 6。
  2. 当您可以选择两个元素时，您不能选择一个元素；当您可以选择三个项目时，您不能选择两个项目。但是，您必须从具有最高优先级（即具有较低索引）的元素开始
  3. 在原始数组中，具有较低索引的元素优先于具有较高索引的元素。那些。$input[0] 比 $input[1] 更重要。优先级，我的意思是它们更优先放置在结果数组中。

示例 1

入口：

(1, 7, 4, 2, 3, 1, 6, 1, 2, 6, 3)

1-的优先级最高，1小于6，直接拿走。我们不取 7，因为 1 + 7 > 6。下一个元素是 4，我们取它，因为 1 + 4 = 5 < 6。我们不取元素 2，因为 5 + 2 = 7 > 6。同样，我们不要取 3。结果，我们得到 (1, 4, 1)

出口：

(1, 4, 1)

示例 2

入口：

(2, 1, 4, 1, 3, 5, 6, 1, 2, 6, 3);

出口：

(2, 1, 1)

示例 3

入口：

(3, 4, 5, 2, 3, 1, 6, 1, 2, 6, 3);

出口：

(3, 2, 1)

例 4

入口：

(7, 4, 5, 2, 3, 1, 6, 1, 2, 6, 3);

出口：

(4, 2)

例 5

入口：

(7, 6, 1, 2, 3, 1, 6, 1, 2, 6, 3);

出口：

(6)

最多结果是“表”。语言不重要（思想重要），PHP更好。

массивы

2 个回答

  1. Best Answer

    是这样的：

    $input = array(1, 7, 4, 2, 3, 1, 6, 1, 2, 6, 3);
$res = array();
$i = 0;
$len = count($input);
while ($i < $len && count($res) < 3)
{
    if (array_sum($res) + $input[$i] <= 6)
        $res[] = $input[$i];
    $i++;
}
var_dump($res);
    • 2

  2. 该问题的正确解决方案如下所示：

    1. 我们设置标准：“最后一个元素的数量最少”。
    2. 我们为 3 个元素实现它，如有必要，为 2 个或一个元素实现。

    虽然看似简单，但这却是一个经典的“背包问题”，需要对最后一个元素的每个数字的选项进行完整的枚举。
    请注意，问题的条件不包含有关初始数字范围的信息（特别是，它们可以是负数）。但这很容易考虑。
    问题的约束使我们能够减少枚举。

    OP 应该使用“贪婪”算法解决问题，该算法并不总是给出正确的结果。

    PHP 程序：

    $samples = [
    [1, 7, 4, 2, 3, 1, 6, 1, 2, 6, 3],
    [2, 1, 4, 1, 3, 5, 6, 1, 2, 6, 3],
    [3, 4, 5, 2, 3, 1, 6, 1, 2, 6, 3],
    [7, 4, 5, 2, 3, 1, 6, 1, 2, 6, 3],
    [7, 6, 1, 2, 3, 1, 6, 1, 2, 6, 3],
    [7, 4, 5, 2, 3, 8, 6, 2, 4, 6, 3],
    [7, 4, 5, 4, 3, 8, 6, 8, 4, 6, 9]
];

function print_m($text, $arr, $level=0){
    $space = str_repeat("&emsp;", $level++);
    echo "$space<b>$text</b>";
    if(gettype($arr)!="array"){
        var_dump($arr);
        return;
    } 
    $flag = false;
    foreach($arr as $value) $flag = $flag || (gettype($value)=="array");
    foreach($arr as $key => $value) {
        if(gettype($value) != "array") {
            echo $flag ? "<br>$key => $value" : "&emsp;$value";
        } else {
            print_m("<br>$space$key => [", $value, $level);
            echo "&emsp;]";
        }
    }
    $level--;
}

foreach ($samples as $key => $values) {
    print_m("<br><br>values = [",$values); echo "&emsp;]<br>";
    $cnt = count($values);
    $minv = min($values);
    $result = null;
    $indmax = $cnt;

    $maxf = 6 - 2*$minv;
    for ($f = 0; $f < $cnt-2; $f++) { 
        if($values[$f] <= $maxf) { //print 111;
            $maxs = 6 - $values[$f] - $minv;
            for ($s = $f+1; $s < $cnt-1; $s++) { 
                if ($values[$s] <= $maxs) { //print 222;
                    $maxt = 6 - $values[$f] - $values[$s];
                    for ($t = $s+1; $t < $cnt; $t++) { 
                        if (($values[$t] <= $maxt) && ($t < $indmax)) { //print 333;
                            $result = [$f=>$values[$f], $s=>$values[$s], $t=>$values[$t]];
                            $indmax = $t;
                            print_m("<br>maximal index is&emsp;$indmax&emsp; for&emsp;[", $result); echo "&emsp;]";
                            break;
                        }
                    }
                }
            }
        }
    }
    if(is_null($result)) {
        $maxf = 6 - $minv;
        for ($f = 0; $f < $cnt-1; $f++) { 
            if($values[$f] <= $maxf){ //print 111;
                $maxs = 6 - $values[$f] - $minv;
                for ($s = $f+1; $s < $cnt; $s++) { 
                    if (($values[$s] <= $maxs) && ($s < $indmax)) { //print 333;
                        $result = [$f=>$values[$f], $s=>$values[$s]];
                        $indmax = $s;
                        print_m("<br>maximal index is&emsp;$indmax&emsp; for&emsp;[", $result); echo "&emsp;]";
                        break;
                    }
                }
            }
        }
    }
    if(is_null($result)) {
        for ($f = 1; $f < $cnt; $f++) { 
            if ($values[$f] <= 6) { //print 333;
                $result = [$f=>$values[$f]];
                $indmax = $f;
                break;
            }
        }
    }
    if(is_null($result)) {
        print "No Solutions";
    } else {
        print_m("<br>Total maximal index is&emsp;$indmax&emsp; for&emsp;[", $result); echo "&emsp;]";
    }
}

    结果：

    
值 = [ 1 7 4 2 3 1 6 1 2 6 3 ]

[ 1 4 1 ] 的最大索引为 5
[ 1 2 3 ] 的最大索引为 4
[ 1 2 3 ] 的总最大索引为 4

值 = [ 2 1 4 1 3 5 6 1 2 6 3 ]

[ 2 1 1 ] 的最大索引为 3
[ 2 1 1 ] 的总最大索引为 3

值 = [ 3 4 5 2 3 1 6 1 2 6 3 ]

[ 3 2 1 ] 的最大索引为 5
[ 3 2 1 ] 的总最大索引为 5

值 = [ 7 4 5 2 3 1 6 1 2 6 3 ]

[ 4 1 1 ] 的最大索引为 7
[ 2 3 1 ] 的最大索引为 5
[ 2 3 1 ] 的总最大索引为 5

值 = [ 7 6 1 2 3 1 6 1 2 6 3 ]

[ 1 2 3 ] 的最大索引为 4
[ 1 2 3 ] 的总最大索引为 4

值 = [ 7 4 5 2 3 8 6 2 4 6 3 ]

[ 2 2 ] 的最大索引为 7
[ 2 2 ] 的总最大指数为 7

值 = [ 7 4 5 4 3 8 6 8 4 6 9 ]

[ 4 ] 的总最大指数为 1
    • 0

相关问题