Хватай и беги

Knapsack.php

<?php

class Knapsack
{
    /**
     * @var Thing[]
     */
    protected $things = [];

    /**
     * Класс реализующий задачу с "рюкзаком" (комбинаторная оптимизация)
     *
     * @param Thing[] $things
     */
    public function __construct(array $things)
    {
        $this->things = $things;
    }


    /**
     * Поиск максимальной выгоды упаковки "рюкзака". При неограниченом рюкзаке.
     *
     * @param int $maxWeight Максимально допустимый вес "рюкзака"
     * @return int Максимальная выгода при оптимизации упаковки
     */
    public function packageMaxCost(int $maxWeight): int
    {
        $resultSet = [0];
        for ($w = 1; $w <= $maxWeight; $w++) {
            $resultSet[$w] = $resultSet[$w - 1];
            foreach ($this->things as $thing) {
                $wThing = $thing->weight;
                if ($wThing <= $w) {
                    $resultSet[$w] = max($resultSet[$w], $resultSet[$w - $wThing] + $thing->cost);
                }
            }
        }

        return $resultSet[$maxWeight];
    }


    /**
     * Поиск максимальной выгоды упаковки "рюкзака". При рюкзаке 0-1.
     *
     * @param int $weight Максимально допустимый вес "рюкзака"
     * @param int $n счетчик
     * @return int Максимальная выгода при оптимизации упаковки
     */
    public function packageOneType($weight, ?int $n = null): int
    {
        if ($n === null) {
            $n = count($this->things);
        }
        if ($n === 0 || $weight === 0) {
            return 0;
        }
        if ($this->things[$n - 1]->weight > $weight) {
            return $this->packageOneType($weight, $n - 1);
        }
        return max(
            $this->things[$n - 1]->cost +
            $this->packageOneType($weight - $this->things[$n - 1]->weight, $n - 1),
            $this->packageOneType($weight, $n - 1)
        );
    }
}

PackageTest.php

<?php namespace Tests\Unit;

use Tests\TestCase;

class KnapsackTest extends TestCase
{
    public function testKnapsackPackageMaxCostSuccess()
    {
        $things = [
            new Thing(2, 17),
            new Thing(3, 30),
            new Thing(6, 75),
        ];
        $knapsack = new Knapsack($things);
        $this->assertEquals(109, $knapsack->packageMaxCost(10));
    }

    public function testKnapsackPackageMaxCostEmpty()
    {
        $things = [];
        $knapsack = new Knapsack($things);
        $this->assertEquals(0, $knapsack->packageMaxCost(10));
        $this->assertEquals(0, $knapsack->packageMaxCost(0));
    }

    public function testKnapsackPackageOneTypeSuccess()
    {
        $things = [
            new Thing(2, 17),
            new Thing(3, 30),
            new Thing(6, 75),
        ];

        $knapsack = new Knapsack($things);
        $this->assertEquals(105, $knapsack->packageOneType(10));
    }

    public function testKnapsackPackageOneTypeEmpty()
    {
        $things = [];
        $knapsack = new Knapsack($things);
        $this->assertEquals(0, $knapsack->packageOneType(10));
        $this->assertEquals(0, $knapsack->packageOneType(0));
    }
}

Thing.php

<?php 

class Thing
{
    /**
     * @var int Вес
     */
    public $weight;
    /**
     * @var int Стоимость
     */
    public $cost;

    /**
     * @param int $weight
     * @param int $cost
     */
    public function __construct(int $weight, int $cost)
    {
        $this->weight = $weight;
        $this->cost = $cost;
    }
}