php - 带项目组的背包方程式

Question

显然不能将其称为 Stack Overflow 上的问题，但我目前正在尝试了解如何在 Knapsack 问题中以项目组的形式集成约束。在这种情况下，我的数学技能被证明是相当有限的，但是我非常有动力让这项工作按预期进行，并弄清楚每个方面的作用(按照这个顺序，因为事情在工作时更有意义)。

话虽如此，我在 Rosetta Code 找到了一个绝对漂亮的实现并清理了一些变量名，以帮助自己从非常基本的角度更好地理解这一点。

不幸的是，我很难弄清楚如何应用此逻辑来包含项目组。我的目的是建立梦幻团队，为每个球员提供我自己的值(value)和权重(积分/薪水)，但没有团体(在我的情况下是职位)我无法这样做。

有人能为此指出正确的方向吗？我正在审查其他语言的代码示例和整个问题的其他描述，但是我希望通过任何可能的方式实现这些组。

<?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, $itemValue, $i-1, $availWeight,$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, $itemValue, ($i-1), ($availWeight - $itemWeight[$i]),$memoItems,$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,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10);

## Initialize
$numcalls = 0;
$memoItems = array();
$selectedItems = array();

## Solve
list ($m4, $selectedItems) = knapSolveFast2($weight, $value, sizeof($value)-1, 400, $memoItems, $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>";

?>

Answer 1

那个背包程序是传统的，但我认为它掩盖了正在发生的事情。让我向您展示如何从蛮力解决方案中更直接地推导出 DP。

在 Python 中(抱歉；这是我选择的脚本语言)，暴力解决方案可能如下所示。首先，有一个使用广度优先搜索生成所有子集的函数(这很重要)。

def all_subsets(S):  # brute force
    subsets_so_far = [()]
    for x in S:
        new_subsets = [subset + (x,) for subset in subsets_so_far]
        subsets_so_far.extend(new_subsets)
    return subsets_so_far

然后有一个函数返回 True 如果解决方案有效(在预算范围内并且具有适当的位置分割) - 称之为 is_valid_solution - 以及一个函数，给定一个解决方案，返回玩家总值(value) (total_player_value)。假设 players 是可用玩家列表，最优解是这样的。

max(filter(is_valid_solution, all_subsets(players)), key=total_player_value)

现在，对于 DP，我们向 all_subsets 添加函数 cull。

def best_subsets(S):  # DP
    subsets_so_far = [()]
    for x in S:
        new_subsets = [subset + (x,) for subset in subsets_so_far]
        subsets_so_far.extend(new_subsets)
        subsets_so_far = cull(subsets_so_far)  ### This is new.
    return subsets_so_far

cull 所做的是丢弃在我们寻找最优解时显然不会遗漏的部分解。如果部分解决方案已经超出预算，或者如果它在一个位置上已经有太多玩家，那么它可以安全地被丢弃。让 is_valid_partial_solution 成为测试这些条件的函数(它可能看起来很像 is_valid_solution)。到目前为止，我们有这个。

def cull(subsets):  # INCOMPLETE!
    return filter(is_valid_partial_solution, subsets)

另一个重要的测试是一些部分解决方案比其他解决方案更好。如果两个部分解决方案具有相同的位置分割(例如，两个前锋和一个中锋)并且成本相同，那么我们只需要保留更有值(value)的那个。让 cost_and_position_breakdown 采取解决方案并生成对指定属性进行编码的字符串。

def cull(subsets):
    best_subset = {}  # empty dictionary/map
    for subset in filter(is_valid_partial_solution, subsets):
        key = cost_and_position_breakdown(subset)
        if (key not in best_subset or
            total_value(subset) > total_value(best_subset[key])):
            best_subset[key] = subset
    return best_subset.values()

就是这样。这里有很多优化要做(例如，丢弃部分解决方案，因为有更便宜和更有值(value)的部分解决方案；修改数据结构，这样我们就不会总是从头开始计算值(value)和头寸分割，并减少存储成本)，但可以逐步解决。