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

Question

Я работаю над 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://stackru.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;
        });
    }
}

Answer 1

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