据说,我在Rosetta Code发现了一个绝对漂亮的实现,并清理了一些变量名,以帮助我从一个非常基本的角度更好的理解这一点.

不幸的是,我有一个难以置信的困难时间,弄清楚我如何应用这个逻辑来包括项目组.我的目的是建立幻想团队,提供我自己的价值&每个玩家的体重(积分/工资),但没有组(我的情况下的位置)我无法这样做.

有人可以指出我正确的方向吗？我正在审查来自其他语言的代码示例以及对整个问题的其他说明,但是我想通过任何可能的方式来实现组.

<?PHP
 
function knapSolveFast2($itemWeight,$itemValue,$i,$availWeight,&$memoItems,&$pickedItems)
{
    global $numcalls;
    $numcalls++;
 
    // Return memo if we have one
    if (isset($memoItems[$i][$availWeight]))
    {
        return array( $memoItems[$i][$availWeight],$memoItems['picked'][$i][$availWeight] );
    }
    else
    {
        // At end of decision branch
        if ($i == 0)
        {
            if ($itemWeight[$i] <= $availWeight)
            { // Will this item fit?
                $memoItems[$i][$availWeight] = $itemValue[$i]; // Memo this item
                $memoItems['picked'][$i][$availWeight] = array($i); // and the picked item
                return array($itemValue[$i],array($i)); // Return the value of this item and add it to the picked list
 
            }
            else
            {
                // Won't fit
                $memoItems[$i][$availWeight] = 0; // Memo zero
                $memoItems['picked'][$i][$availWeight] = array(); // and a blank array entry...
                return array(0,array()); // Return nothing
            }
        }   
 
        // Not at end of decision branch..
        // Get the result of the next branch (without this one)
        list ($without_i,$without_PI) = knapSolveFast2($itemWeight,$i-1,$memoItems,$pickedItems);
 
        if ($itemWeight[$i] > $availWeight)
        { // Does it return too many?
            $memoItems[$i][$availWeight] = $without_i; // Memo without including this one
            $memoItems['picked'][$i][$availWeight] = array(); // and a blank array entry...
            return array($without_i,array()); // and return it
        }
        else
        {
            // Get the result of the next branch (WITH this one picked,so available weight is reduced)
            list ($with_i,$with_PI) = knapSolveFast2($itemWeight,($i-1),($availWeight - $itemWeight[$i]),$pickedItems);
            $with_i += $itemValue[$i];  // ..and add the value of this one..
 
            // Get the greater of WITH or WITHOUT
            if ($with_i > $without_i)
            {
                $res = $with_i;
                $picked = $with_PI;
                array_push($picked,$i);
            }
            else
            {
                $res = $without_i;
                $picked = $without_PI;
            }
 
            $memoItems[$i][$availWeight] = $res; // Store it in the memo
            $memoItems['picked'][$i][$availWeight] = $picked; // and store the picked item
            return array ($res,$picked); // and then return it
        }   
    }
}
 
$items = array("map","compass","water","sandwich","glucose","tin","banana","apple","cheese","beer","suntan cream","camera","t-shirt","trousers","umbrella","waterproof trousers","waterproof overclothes","note-case","sunglasses","towel","socks","book");
$weight = array(9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30);
$value = array(150,35,200,160,60,45,40,30,10,70,75,80,20,12,10);
 
## Initialize
$numcalls = 0;
$memoItems = array();
$selectedItems = array();
 
## Solve
list ($m4,$selectedItems) = knapSolveFast2($weight,$value,sizeof($value)-1,400,$selectedItems);
 
# Display Result 
echo "<b>Items:</b><br>" . join(",",$items) . "<br>";
echo "<b>Max Value Found:</b><br>$m4 (in $numcalls calls)<br>";
echo "<b>Array Indices:</b><br>". join(",$selectedItems) . "<br>";
 
echo "<b>Chosen Items:</b><br>";
echo "<table border cellspacing=0>";
echo "<tr><td>Item</td><td>Value</td><td>Weight</td></tr>";
 
$totalValue = 0;
$totalWeight = 0;
 
foreach($selectedItems as $key)
{
    $totalValue += $value[$key];
    $totalWeight += $weight[$key];
 
    echo "<tr><td>" . $items[$key] . "</td><td>" . $value[$key] . "</td><td>".$weight[$key] . "</td></tr>";
}
 
echo "<tr><td align=right><b>Totals</b></td><td>$totalValue</td><td>$totalWeight</td></tr>";
echo "</table><hr>";
 
?>