10 html php algorithm math knapsack-problem
在Stack Overflow上显然无法将其称为问题,但我目前正在尝试了解如何在背包问题中以项目组的形式集成约束.在这种情况下,我的数学技能被证明是相当有限的,但我非常积极地使这项工作按预期进行,并弄清楚每个方面的作用(按顺序,因为事情在工作时更有意义).
话虽如此,我已经在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, $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>";
?>
背包程序是传统的，但我认为它掩盖了正在发生的事情。让我向您展示如何从强力解决方案中更直接地导出 DP。
\n\n在 Python 中（抱歉；这是我选择的脚本语言），强力解决方案可能如下所示。首先，有一个函数用于通过广度优先搜索生成所有子集（这很重要）。
\n\ndef all_subsets(S): # brute force\n subsets_so_far = [()]\n for x in S:\n new_subsets = [subset + (x,) for subset in subsets_so_far]\n subsets_so_far.extend(new_subsets)\n return subsets_so_far\n然后，True如果解决方案有效（在预算范围内并具有适当的位置细分） \xe2\x80\x93 ，则有一个函数返回，称为is_valid_solution\xe2\x80\x93 ，还有一个函数，在给定解决方案的情况下，返回玩家总价值（total_player_value）。假设这players是可用玩家的列表，则最佳解决方案是这样的。
max(filter(is_valid_solution, all_subsets(players)), key=total_player_value)\n现在，对于 DP，我们cull向 中添加一个函数all_subsets。
def best_subsets(S): # DP\n subsets_so_far = [()]\n for x in S:\n new_subsets = [subset + (x,) for subset in subsets_so_far]\n subsets_so_far.extend(new_subsets)\n subsets_so_far = cull(subsets_so_far) ### This is new.\n return subsets_so_far\n所做cull的就是丢弃在我们寻找最佳解决方案时显然不会错过的部分解决方案。如果部分解决方案已经超出预算，或者某个位置上已经有太多球员，那么可以安全地放弃它。Letis_valid_partial_solution是一个测试这些条件的函数（它可能看起来很像is_valid_solution）。到目前为止我们已经有了这个。
def cull(subsets): # INCOMPLETE!\n return filter(is_valid_partial_solution, subsets)\n另一个重要的测试是某些部分解决方案比其他解决方案更好。如果两个部分解决方案具有相同的位置细分（例如，两个前锋和一个中锋）并且成本相同，那么我们只需要保留更有价值的一个。让我们cost_and_position_breakdown采取一个解决方案并生成一个对指定属性进行编码的字符串。
def cull(subsets):\n best_subset = {} # empty dictionary/map\n for subset in filter(is_valid_partial_solution, subsets):\n key = cost_and_position_breakdown(subset)\n if (key not in best_subset or\n total_value(subset) > total_value(best_subset[key])):\n best_subset[key] = subset\n return best_subset.values()\n就是这样。这里需要做很多优化（例如，丢弃部分解决方案，因为有更便宜且更有价值的部分解决方案；修改数据结构，以便我们不必总是从头开始计算价值和位置细分，并减少存储成本），但可以逐步解决。
\n