Pick/Sort算法（背包）

Question

我在执行任务时遇到了问题。我有一个数据库，其中的项目都具有 "price" 值。它们连接到不同的 "rounds" 并且 "rounds" 有一个 "tot-value"，其中这些项目 "price"-值全部放在一起定义 "tot-value"。所以，我想选择哪些物品可以赠送，哪些可以保存。 "tot-value" 的 5% 到 10% 应该被保存下来，其余的被送走。

我可以 select 那轮中的所有项目，按 "price" 值排序，从最低到最高，然后：

if ($totSave < $totVal*0.1) { addToSaveArray($item); $totSave += $item['price']; }

但我也有一个应该优先考虑项目的列表，设置如下：

$prioList[] = array("name" => $list[$i], "price" => $price);

那么，最好的方法是什么？我是否循环遍历 $prioList，检查是否有任何名称匹配，然后将价格添加到 $totSave 或您认为如何？

非常感谢您的帮助！

Answer 1

Jim 让我 post 回答，所以这就是我正在做的 :) 因为这是一个背包问题，我用 google 搜索并找到了这个： https://github.com/acmeism/RosettaCodeData/tree/master/Task/Knapsack-problem-0-1/PHP

我也需要索引，所以我选择了最上面的（有问题的）索引。（不能 post link 由于低代表...）

因为那个有问题，我添加了一个 "try" 函数。这里是： http://pastebin.com/AycE4Kzm

Pick/Sort算法（背包）

Pick/Sort Algorithm (Knapsack)

php

sorting

algorithm

knapsack-problem