README

PHP应用程序中背包问题的解决方案。

可用算法

使用示例

<?php

use Writ3it\LibAlgo\KnapsackProblem\Impl\Item;
use Writ3it\LibAlgo\KnapsackProblem\Impl\Bag;
use Writ3it\LibAlgo\KnapsackProblem\Algorithm\DynamicKnapsackSolver;

$items = [
    // new Item(<weight>, <value f.e. price>)
    new Item(2, 4), /** Item 0 **/
    new Item(1, 3), /** Item 1 **/
    new Item(4, 6), /** Item 2 **/
    new Item(4, 8)  /** Item 3 **/
];

// new Bag(<capacity>)
$bag = new Bag(8); 

$algo = new DynamicKnapsackSolver();
$value = $algo->solve($items, $bag);

var_dump([

     // Item 0,1,3 which are optimal content of the bag.
    'content'=>$bag->getItems(), 

     // Summary value of items in bag.
    'value' =>$value 

]);

自定义项目

一个项目可以是任何PHP对象。有时，你可能需要用比Item类更复杂的对象来模拟你的逻辑。你可以通过在自己的项目中实现ItemInterface来实现这一点

<?php

use Writ3it\LibAlgo\KnapsackProblem\ItemInterface;

class CustomItem implements ItemInterface
{

    
    /**
     * {@inheritdoc}
     */
    public function getWeight(): int
    {
        // Custom logic to compute a weight.
    }
    
    /**
     * {@inheritdoc}
     */
    public function getValue(): int
    {
        // Custom logic to compute a value.
    }

    /**
     * More your own methods
     */

}

解决背包问题的有效算法要求在求解器运行时间内，重量和价值必须是整数且为常量。

自定义包

一个包可以是任何PHP对象。有时，你可能需要用比Bag类更复杂的对象来模拟你的逻辑。你可以通过在自己的项目中实现BagInterface来实现这一点

<?php

use Writ3it\LibAlgo\KnapsackProblem\ItemInterface;

class CustomBag implements BagInterface
{

    
    public function getCapacity(): int
    {
       // Custom logic to compute a capacity.
    }

    public function addItem(ItemInterface $item): void
    {
        // Custom logic to receive a items which are a solution.
    }

    /**
     * More your own methods
     */

}