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 ]

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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