2

Пусть у нас есть некоторый массив, состоящий из чисел, например такой:

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

5
  • Условие "три или менее" приводит к просто первому элементу, не превышающему 6.
    – Harry
    25 мар 2017 в 13:08
  • спасибо, сейчас поправлю
    – pynista
    25 мар 2017 в 13:10
  • Тогда еще - для (1, 7, 4, 2, 3, 1, 6, 1, 2, 6, 3) - что будет ответом? (1,4), (4,2) или (1,4,1)?
    – Harry
    25 мар 2017 в 13:15
  • 1- имеет самый высокий приоритет, и единица меньше 6, поэтому ее сразу берем. 7 не берем потому что 1 + 7 > 6. Следующий элемент 4, его берем, потому- что 1 + 4 = 5 < 6. Элемент 2 не берем, потому что 5 + 2 = 7 > 6. Аналогично, не берем 3. В результате, получаем (1, 4, 1)
    – pynista
    25 мар 2017 в 13:19
  • Для этой задачи "жадного" алгоритма недостаточно, потому что фактически приоритет элементов определяется размером минимально необходимого подмассива. 5 апр 2017 в 11:17

2 ответа 2

2

Что-то в это роде:

$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);
0

Корректное решение задачи выглядит так:

  1. Задаёмся критерием: "Номер последнего элемента минимален".
  2. Реализуем его для 3 и при необходимости - 2 или одного элемента.

При кажущейся простоте, это классическая "задача о рюкзаке", которая требует полного перебора вариантов по каждому номеру последнего элемента.
Заметим, что условия задачи не содержат сведений о диапазоне исходных чисел (в частности, они могут быть отрицательными). Но его нетрудно учесть.
Ограничения задачи позволяют сократить перебор.

В ОП предполагается решение задачи по "жадному" алгоритму, который не всегда даёт правильный результат.

Программа на 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;]";
    }
}

Результаты:



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

maximal index is 5  for [ 1 4 1 ]
maximal index is 4  for [ 1 2 3 ]
Total maximal index is 4  for [ 1 2 3 ]

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

maximal index is 3  for [ 2 1 1 ]
Total maximal index is 3  for [ 2 1 1 ]

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

maximal index is 5  for [ 3 2 1 ]
Total maximal index is 5  for [ 3 2 1 ]

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

maximal index is 7  for [ 4 1 1 ]
maximal index is 5  for [ 2 3 1 ]
Total maximal index is 5  for [ 2 3 1 ]

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

maximal index is 4  for [ 1 2 3 ]
Total maximal index is 4  for [ 1 2 3 ]

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

maximal index is 7  for [ 2 2 ]
Total maximal index is 7  for [ 2 2 ]

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

Total maximal index is 1  for [ 4 ]

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.