PHP: пазл с монетами

Я работаю над Advent of Code, чтобы практиковать TDD и изучать PHPSpec. Я застрял в 17-й день, который, по сути, представляет собой головоломку для смены монет.

Эльфы снова купили слишком много eggnog — на этот раз 150 литров. Чтобы поместить все это в ваш холодильник, вам нужно переместить его в меньшие контейнеры. Вы проводите инвентаризацию вместимости имеющихся контейнеров.

Например, предположим, у вас есть контейнеры объемом 20, 15, 10, 5 и 5 литров. Если вам нужно хранить 25 литров, есть четыре способа сделать это:

  • 15 и 10
  • 20 и 5 (первые 5)
  • 20 и 5 (вторая 5)
  • 15, 5 и 5

Полностью заполняя все контейнеры, сколько различных комбинаций контейнеров может вмещать все 150 литров eggnog?

Вот мой код Я написал тест, используя примеры выше. combinations метод должен вернуться 4 согласно примеру, но возвращает 3. Похоже, он не в состоянии справиться с тем фактом, что имеется более одного контейнера объемом 5 литров.

Любые предложения, пожалуйста?

<?php

namespace Day17;

class Calculator
{
private $containers = [];

public function combinations($total, array $containers)
{
$combinations = $this->iterate($total, $containers);
return count($combinations);
}

/**
* http://stackoverflow.com/questions/12837431/find-combinations-sum-of-elements-in-array-whose-sum-equal-to-a-given-number
*
* @param $array
* @param array $combinations
* @param array $temp
* @return array
*/
private function iterate($sum, $array, $combinations = [], $temp = [])
{
if (count($temp) && !in_array($temp, $combinations)) {
$combinations[] = $temp;
}

$count = count($array);
for ($i = 0; $i < $count; $i++) {

$copy = $array;
$elem = array_splice($copy, $i, 1);

if (count($copy) > 0) {

$add = array_merge($temp, array($elem[0]));
sort($add);
$combinations = $this->iterate($sum, $copy, $combinations, $add);

} else {

$add = array_merge($temp, array($elem[0]));
sort($add);
if (array_sum($combinations) == $sum) {
$combinations[] = $add;
}
}
}

return array_filter($combinations, function ($combination) use ($sum) {
return array_sum($combination) == $sum;
});
}
}

1

Решение

Используйте индексы массива доступных контейнеров в качестве значений комбинации.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]