用动态规划解决多项选择背包 (MCKP)？
Solve Multiple Choice Knapsack (MCKP) With Dynamic Programming?
示例数据
对于这个问题，我们假设以下项目：
- 项目：苹果、香蕉、胡萝卜、牛排、洋葱
- 值：2、2、4、5、3
- 权重：3、1、3、4、2
- 最大重量：7
Objective:
MCKP 是 Knapsack Problem 的一种类型，具有附加约束“[T] 项目被细分为 k classes... 并且必须从每个 class
中取出一个项目
我已经编写了使用递归调用和记忆的动态编程来解决 0/1 KS 问题的代码。我的问题是是否可以将此约束添加到我当前的解决方案中？假设我的 classes 是水果、蔬菜、肉类（来自示例），我需要包括每种类型的 1 个。 classes 也可以是类型 1、2、3。
此外，我认为这可以通过线性规划和求解器来解决，但如果可能的话，我想在这里了解答案。
当前代码：
<?php
$value = array(2, 2, 4, 5, 3);
$weight = array(3, 1, 3, 4, 2);
$maxWeight = 7;
$maxItems = 5;
$seen = array(array()); //2D array for memoization
$picked = array();
//Put a dummy zero at the front to make things easier later.
array_unshift($value, 0);
array_unshift($weight, 0);
//Call our Knapsack Solver and return the sum value of optimal set
$KSResult = KSTest($maxItems, $maxWeight, $value, $weight);
$maxValue = $KSResult; //copy the result so we can recreate the table
//Recreate the decision table from our memo array to determine what items were picked
//Here I am building the table backwards because I know the optimal value will be at the end
for($i=$maxItems; $i > 0; $i--) {
for($j=$maxWeight; $j > 0; $j--) {
if($seen[$i][$j] != $seen[$i-1][$j]
&& $maxValue == $seen[$i][$j]) {
array_push($picked, $i);
$maxValue -= $value[$i];
break;
}
}
}
//Print out picked items and max value
print("<pre>".print_r($picked,true)."</pre>");
echo $KSResult;
// Recursive formula to solve the KS Problem
// $n = number of items to check
// $c = total capacity of bag
function KSTest($n, $c, &$value, &$weight) {
global $seen;
if(isset($seen[$n][$c])) {
//We've seen this subproblem before
return $seen[$n][$c];
}
if($n === 0 || $c === 0){
//No more items to check or no more capacity
$result = 0;
}
elseif($weight[$n] > $c) {
//This item is too heavy, check next item without this one
$result = KSTest($n-1, $c, $value, $weight);
}
else {
//Take the higher result of keeping or not keeping the item
$tempVal1 = KSTest($n-1, $c, $value, $weight);
$tempVal2 = $value[$n] + KSTest($n-1, $c-$weight[$n], $value, $weight);
if($tempVal2 >= $tempVal1) {
$result = $tempVal2;
//some conditions could go here? otherwise use max()
}
else {
$result = $tempVal1;
}
}
//memo the results and return
$seen[$n][$c] = $result;
return $result;
}
?>
我尝试过的：
- 我的第一个想法是添加一个class(k)数组，通过class(k)对item进行排序，当我们选择select一个item时，就是与下一项相同，检查是否保留当前项目或没有下一项的项目更好。看起来很有希望，但在检查了几项之后就崩溃了。是这样的：
$tempVal3 = $value[$n] + KSTest($n-2, $c-$weight[$n]);
最大值（$tempVal2，$tempVal3）；
- 另一个想法是，在函数调用时，我可以为每个 class 类型调用一个循环，并一次仅使用该类型的 1 项 + 其余值来求解 KS。这肯定会做出一些假设，因为第 1 组的结果可能仍然假设第 2 组的倍数，例如。
This looks to be the equation（如果您擅长阅读所有这些符号？）:) 和 C++ 实现？但我真的看不出 class 约束在哪里发生？
所以我不是 php 程序员，但我会尝试编写一个有很好解释的伪代码。
在原始问题中，每个单元格 i, j 的含义是："Value of filling the knapsack with items 1 to i until it reach capacity j"，您提供的 link 中的解决方案将每个单元格定义为 "Value of filling the knapsack with items from buckets 1 to i until it reach capacity j"。请注意，在这种变体中，不存在不从 class.
中获取元素的情况。
所以在每一步（每次调用 KSTest 和 $n、$c），我们需要找到从第 n 个 class 中选择哪个元素这样这个元素的权重小于c和它的值+KSTest(n - 1, c - w)是最大的。
所以我认为您应该只将 else if 和 else 语句更改为：
else {
$result = 0
for($i=0; $i < $number_of_items_in_nth_class; $i++) {
if ($weight[$n][$i] > $c) {
//This item is too heavy, check next item
continue;
}
$result = max($result, KSTest($n-1, $c - $weight[$n][$i], $value, $weight));
}
}
现在有两个免责声明：
我没有在 php 中编码，所以这段代码不会 运行 :)
这不是你提供的link中给出的实现，TBH我不明白为什么他们算法的时间复杂度这么小（什么是C) 但此实现 应该 有效，因为它遵循给定的递归公式的定义。
这个的时间复杂度应该是O(max_weight * number_of_classes * size_of_largerst_class).
C++ 实现看起来不错。
您当前 PHP 实施中的一维数组的值和权重将变为二维。
例如，
values[i][j] 将是 class i 中第 j 项的值。在 weights[i][j] 的情况下也是如此。每个 class i 您将只拿取一件物品并在最大化条件的同时继续前进。
c++实现也在备忘录中做了优化。它只保留 2 个大小符合 max_weight 条件的数组，它们是当前状态和先前状态。这是因为您一次只需要这 2 个状态来计算当前状态。
解答你的疑惑：
1)
My first thought was to add a class (k) array, sort the items via
class (k), and when we choose to select an item that is the same as
the next item, check if it's better to keep the current item or the
item without the next item. Seemed promising, but fell apart after a
couple of items being checked. Something like this: $tempVal3 =
$value[$n] + KSTest($n-2, $c-$weight[$n]); max( $tempVal2, $tempVal3);
这是行不通的，因为 class k+1 中可能有一些项目您取了最优值，为了尊重约束，您需要为 class k 取次优值。因此，当约束被击中时，排序和挑选最好的将不起作用。如果未达到约束，您始终可以选择具有最佳权重的最佳值。
2)
Another thought is that at the function call, I could call a loop for
each class type and solve the KS with only 1 item at a time of that
type + the rest of the values.
是的，您走在正确的轨道上。你会假设你已经解决了前 k classes。现在您将尝试根据权重约束使用 k+1 class 的值进行扩展。
3)
... but I can't really see where the class constraint is happening?
for (int i = 1; i < weight.size(); ++i) {
fill(current.begin(), current.end(), -1);
for (int j = 0; j < weight[i].size(); ++j) {
for (int k = weight[i][j]; k <= max_weight; ++k) {
if (last[k - weight[i][j]] > 0)
current[k] = max(current[k],
last[k - weight[i][j]] + value[i][j]);
}
}
swap(current, last);
}
在上面的 c++ 片段中，第一个循环迭代 class，第二个循环迭代 class 的值，第三个循环使用前一个循环扩展当前状态 current状态 last 并且一次只有 1 项 j class i。由于您仅使用先前状态 last 和当前状态 class 的 1 项来扩展和最大化，因此您遵循约束。
时间复杂度：
O( total_items x max_weight) 相当于 O( class x max_number_of_items_in_a_class x max_weight)
这是我的 PHP 解决方案。我尝试以一种易于理解的方式对代码进行注释。
更新：
我更新了代码，因为旧脚本给出了不可靠的结果。这更清洁，并且已经过彻底测试。关键要点是我使用了两个备忘录数组，一个在组级别以加快执行速度，一个在项目级别以重建结果。我发现任何尝试跟踪您选择的项目都是不可靠的，而且效率低得多。此外，isset() 而不是 if($var) 对于检查备忘录数组是必不可少的，因为之前的结果可能是 0 ;)
<?php
/**
* Multiple Choice Knapsack Solver
*
* @author Michael Cruz
* @version 1.0 - 03/27/2020
**/
class KS_Solve {
public $KS_Items;
public $maxValue;
public $maxWeight;
public $maxItems;
public $finalValue;
public $finalWeight;
public $finalItems;
public $finalGroups;
public $memo1 = array(); //Group memo
public $memo2 = array(); //Item memo for results rebuild
public function __construct() {
//some default variables as an example.
//KS_Items = array(Value, Weight, Group, Item #)
$this->KS_Items = array(
array(2, 3, 1, 1),
array(2, 1, 1, 2),
array(4, 3, 2, 3),
array(5, 4, 2, 4),
array(3, 2, 3, 5)
);
$this->maxWeight = 7;
$this->maxItems = 5;
$this->KS_Wrapper();
}
public function KS_Wrapper() {
$start_time = microtime(true);
//Put a dummy zero at the front to make things easier later.
array_unshift($this->KS_Items, array(0, 0, 0, 0));
//Call our Knapsack Solver
$this->maxValue = $this->KS_Solver($this->maxItems, $this->maxWeight);
//Recreate the decision table from our memo array to determine what items were picked
//ksort($this->memo2); //for debug
for($i=$this->maxItems; $i > 0; $i--) {
//ksort($this->memo2[$i]); //for debug
for($j=$this->maxWeight; $j > 0; $j--) {
if($this->maxValue == 0) {
break 2;
}
if($this->memo2[$i][$j] == $this->maxValue
&& $j == $this->maxWeight) {
$this->maxValue -= $this->KS_Items[$i][0];
$this->maxWeight -= $this->KS_Items[$i][1];
$this->finalValue += $this->KS_Items[$i][0];
$this->finalWeight += $this->KS_Items[$i][1];
$this->finalItems .= " " . $this->KS_Items[$i][3];
$this->finalGroups .= " " . $this->KS_Items[$i][2];
break;
}
}
}
//Print out the picked items and value. (IMPLEMENT Proper View or Return!)
echo "<pre>";
echo "RESULTS: <br>";
echo "Value: " . $this->finalValue . "<br>";
echo "Weight: " . $this->finalWeight . "<br>";
echo "Item's in KS:" . $this->finalItems . "<br>";
echo "Selected Groups:" . $this->finalGroups . "<br><br>";
$end_time = microtime(true);
$execution_time = ($end_time - $start_time);
echo "Results took " . sprintf('%f', $execution_time) . " seconds to execute<br>";
}
/**
* Recursive function to solve the MCKS Problem
* $n = number of items to check
* $c = total capacity of KS
**/
public function KS_Solver($n, $c) {
$group = $this->KS_Items[$n][2];
$groupItems = array();
$count = 0;
$result = 0;
$bestVal = 0;
if(isset($this->memo1[$group][$c])) {
$result = $this->memo1[$group][$c];
}
else {
//Sort out the items for this group
foreach($this->KS_Items as $item) {
if($item[2] == $group) {
$groupItems[] = $item;
$count++;
}
}
//$k adjusts the index for item memoization
$k = $count - 1;
//Find the results of each item + items of other groups
foreach($groupItems as $item) {
if($item[1] > $c) {
//too heavy
$result = 0;
}
elseif($item[1] >= $c && $group != 1) {
//too heavy for next group
$result = 0;
}
elseif($group == 1) {
//Just take the highest value
$result = $item[0];
}
else {
//check this item with following groups
$result = $item[0] + $this->KS_Solver($n - $count, $c - $item[1]);
}
if($result == $item[0] && $group != 1) {
//No solution with the following sets, so don't use this item.
$result = 0;
}
if($result > $bestVal) {
//Best item so far
$bestVal = $result;
}
//memo the results
$this->memo2[$n-$k][$c] = $result;
$k--;
}
$result = $bestVal;
}
//memo and return
$this->memo1[$group][$c] = $result;
return $result;
}
}
new KS_Solve();
?>
示例数据
对于这个问题，我们假设以下项目：
- 项目：苹果、香蕉、胡萝卜、牛排、洋葱
- 值：2、2、4、5、3
- 权重：3、1、3、4、2
- 最大重量：7
Objective:
MCKP 是 Knapsack Problem 的一种类型，具有附加约束“[T] 项目被细分为 k classes... 并且必须从每个 class
中取出一个项目我已经编写了使用递归调用和记忆的动态编程来解决 0/1 KS 问题的代码。我的问题是是否可以将此约束添加到我当前的解决方案中？假设我的 classes 是水果、蔬菜、肉类（来自示例），我需要包括每种类型的 1 个。 classes 也可以是类型 1、2、3。
此外，我认为这可以通过线性规划和求解器来解决，但如果可能的话，我想在这里了解答案。
当前代码：
<?php
$value = array(2, 2, 4, 5, 3);
$weight = array(3, 1, 3, 4, 2);
$maxWeight = 7;
$maxItems = 5;
$seen = array(array()); //2D array for memoization
$picked = array();
//Put a dummy zero at the front to make things easier later.
array_unshift($value, 0);
array_unshift($weight, 0);
//Call our Knapsack Solver and return the sum value of optimal set
$KSResult = KSTest($maxItems, $maxWeight, $value, $weight);
$maxValue = $KSResult; //copy the result so we can recreate the table
//Recreate the decision table from our memo array to determine what items were picked
//Here I am building the table backwards because I know the optimal value will be at the end
for($i=$maxItems; $i > 0; $i--) {
for($j=$maxWeight; $j > 0; $j--) {
if($seen[$i][$j] != $seen[$i-1][$j]
&& $maxValue == $seen[$i][$j]) {
array_push($picked, $i);
$maxValue -= $value[$i];
break;
}
}
}
//Print out picked items and max value
print("<pre>".print_r($picked,true)."</pre>");
echo $KSResult;
// Recursive formula to solve the KS Problem
// $n = number of items to check
// $c = total capacity of bag
function KSTest($n, $c, &$value, &$weight) {
global $seen;
if(isset($seen[$n][$c])) {
//We've seen this subproblem before
return $seen[$n][$c];
}
if($n === 0 || $c === 0){
//No more items to check or no more capacity
$result = 0;
}
elseif($weight[$n] > $c) {
//This item is too heavy, check next item without this one
$result = KSTest($n-1, $c, $value, $weight);
}
else {
//Take the higher result of keeping or not keeping the item
$tempVal1 = KSTest($n-1, $c, $value, $weight);
$tempVal2 = $value[$n] + KSTest($n-1, $c-$weight[$n], $value, $weight);
if($tempVal2 >= $tempVal1) {
$result = $tempVal2;
//some conditions could go here? otherwise use max()
}
else {
$result = $tempVal1;
}
}
//memo the results and return
$seen[$n][$c] = $result;
return $result;
}
?>
我尝试过的：
- 我的第一个想法是添加一个class(k)数组，通过class(k)对item进行排序，当我们选择select一个item时，就是与下一项相同，检查是否保留当前项目或没有下一项的项目更好。看起来很有希望，但在检查了几项之后就崩溃了。是这样的： $tempVal3 = $value[$n] + KSTest($n-2, $c-$weight[$n]); 最大值（$tempVal2，$tempVal3）；
- 另一个想法是，在函数调用时，我可以为每个 class 类型调用一个循环，并一次仅使用该类型的 1 项 + 其余值来求解 KS。这肯定会做出一些假设，因为第 1 组的结果可能仍然假设第 2 组的倍数，例如。
This looks to be the equation（如果您擅长阅读所有这些符号？）:) 和 C++ 实现？但我真的看不出 class 约束在哪里发生？
所以我不是 php 程序员，但我会尝试编写一个有很好解释的伪代码。
在原始问题中，每个单元格 i, j 的含义是："Value of filling the knapsack with items 1 to i until it reach capacity j"，您提供的 link 中的解决方案将每个单元格定义为 "Value of filling the knapsack with items from buckets 1 to i until it reach capacity j"。请注意，在这种变体中，不存在不从 class.
所以在每一步（每次调用 KSTest 和 $n、$c），我们需要找到从第 n 个 class 中选择哪个元素这样这个元素的权重小于c和它的值+KSTest(n - 1, c - w)是最大的。
所以我认为您应该只将 else if 和 else 语句更改为：
else {
$result = 0
for($i=0; $i < $number_of_items_in_nth_class; $i++) {
if ($weight[$n][$i] > $c) {
//This item is too heavy, check next item
continue;
}
$result = max($result, KSTest($n-1, $c - $weight[$n][$i], $value, $weight));
}
}
现在有两个免责声明：
我没有在 php 中编码，所以这段代码不会 运行 :)
这不是你提供的link中给出的实现，TBH我不明白为什么他们算法的时间复杂度这么小（什么是
C) 但此实现 应该 有效，因为它遵循给定的递归公式的定义。
这个的时间复杂度应该是O(max_weight * number_of_classes * size_of_largerst_class).
C++ 实现看起来不错。
您当前 PHP 实施中的一维数组的值和权重将变为二维。
例如，
values[i][j] 将是 class i 中第 j 项的值。在 weights[i][j] 的情况下也是如此。每个 class i 您将只拿取一件物品并在最大化条件的同时继续前进。
c++实现也在备忘录中做了优化。它只保留 2 个大小符合 max_weight 条件的数组，它们是当前状态和先前状态。这是因为您一次只需要这 2 个状态来计算当前状态。
解答你的疑惑：
1)
My first thought was to add a class (k) array, sort the items via class (k), and when we choose to select an item that is the same as the next item, check if it's better to keep the current item or the item without the next item. Seemed promising, but fell apart after a couple of items being checked. Something like this: $tempVal3 = $value[$n] + KSTest($n-2, $c-$weight[$n]); max( $tempVal2, $tempVal3);
这是行不通的，因为 class k+1 中可能有一些项目您取了最优值，为了尊重约束，您需要为 class k 取次优值。因此，当约束被击中时，排序和挑选最好的将不起作用。如果未达到约束，您始终可以选择具有最佳权重的最佳值。
2)
Another thought is that at the function call, I could call a loop for each class type and solve the KS with only 1 item at a time of that type + the rest of the values.
是的，您走在正确的轨道上。你会假设你已经解决了前 k classes。现在您将尝试根据权重约束使用 k+1 class 的值进行扩展。
3)
... but I can't really see where the class constraint is happening?
for (int i = 1; i < weight.size(); ++i) {
fill(current.begin(), current.end(), -1);
for (int j = 0; j < weight[i].size(); ++j) {
for (int k = weight[i][j]; k <= max_weight; ++k) {
if (last[k - weight[i][j]] > 0)
current[k] = max(current[k],
last[k - weight[i][j]] + value[i][j]);
}
}
swap(current, last);
}
在上面的 c++ 片段中，第一个循环迭代 class，第二个循环迭代 class 的值，第三个循环使用前一个循环扩展当前状态 current状态 last 并且一次只有 1 项 j class i。由于您仅使用先前状态 last 和当前状态 class 的 1 项来扩展和最大化，因此您遵循约束。
时间复杂度：
O( total_items x max_weight) 相当于 O( class x max_number_of_items_in_a_class x max_weight)
这是我的 PHP 解决方案。我尝试以一种易于理解的方式对代码进行注释。
更新： 我更新了代码，因为旧脚本给出了不可靠的结果。这更清洁，并且已经过彻底测试。关键要点是我使用了两个备忘录数组，一个在组级别以加快执行速度，一个在项目级别以重建结果。我发现任何尝试跟踪您选择的项目都是不可靠的，而且效率低得多。此外，isset() 而不是 if($var) 对于检查备忘录数组是必不可少的，因为之前的结果可能是 0 ;)
<?php
/**
* Multiple Choice Knapsack Solver
*
* @author Michael Cruz
* @version 1.0 - 03/27/2020
**/
class KS_Solve {
public $KS_Items;
public $maxValue;
public $maxWeight;
public $maxItems;
public $finalValue;
public $finalWeight;
public $finalItems;
public $finalGroups;
public $memo1 = array(); //Group memo
public $memo2 = array(); //Item memo for results rebuild
public function __construct() {
//some default variables as an example.
//KS_Items = array(Value, Weight, Group, Item #)
$this->KS_Items = array(
array(2, 3, 1, 1),
array(2, 1, 1, 2),
array(4, 3, 2, 3),
array(5, 4, 2, 4),
array(3, 2, 3, 5)
);
$this->maxWeight = 7;
$this->maxItems = 5;
$this->KS_Wrapper();
}
public function KS_Wrapper() {
$start_time = microtime(true);
//Put a dummy zero at the front to make things easier later.
array_unshift($this->KS_Items, array(0, 0, 0, 0));
//Call our Knapsack Solver
$this->maxValue = $this->KS_Solver($this->maxItems, $this->maxWeight);
//Recreate the decision table from our memo array to determine what items were picked
//ksort($this->memo2); //for debug
for($i=$this->maxItems; $i > 0; $i--) {
//ksort($this->memo2[$i]); //for debug
for($j=$this->maxWeight; $j > 0; $j--) {
if($this->maxValue == 0) {
break 2;
}
if($this->memo2[$i][$j] == $this->maxValue
&& $j == $this->maxWeight) {
$this->maxValue -= $this->KS_Items[$i][0];
$this->maxWeight -= $this->KS_Items[$i][1];
$this->finalValue += $this->KS_Items[$i][0];
$this->finalWeight += $this->KS_Items[$i][1];
$this->finalItems .= " " . $this->KS_Items[$i][3];
$this->finalGroups .= " " . $this->KS_Items[$i][2];
break;
}
}
}
//Print out the picked items and value. (IMPLEMENT Proper View or Return!)
echo "<pre>";
echo "RESULTS: <br>";
echo "Value: " . $this->finalValue . "<br>";
echo "Weight: " . $this->finalWeight . "<br>";
echo "Item's in KS:" . $this->finalItems . "<br>";
echo "Selected Groups:" . $this->finalGroups . "<br><br>";
$end_time = microtime(true);
$execution_time = ($end_time - $start_time);
echo "Results took " . sprintf('%f', $execution_time) . " seconds to execute<br>";
}
/**
* Recursive function to solve the MCKS Problem
* $n = number of items to check
* $c = total capacity of KS
**/
public function KS_Solver($n, $c) {
$group = $this->KS_Items[$n][2];
$groupItems = array();
$count = 0;
$result = 0;
$bestVal = 0;
if(isset($this->memo1[$group][$c])) {
$result = $this->memo1[$group][$c];
}
else {
//Sort out the items for this group
foreach($this->KS_Items as $item) {
if($item[2] == $group) {
$groupItems[] = $item;
$count++;
}
}
//$k adjusts the index for item memoization
$k = $count - 1;
//Find the results of each item + items of other groups
foreach($groupItems as $item) {
if($item[1] > $c) {
//too heavy
$result = 0;
}
elseif($item[1] >= $c && $group != 1) {
//too heavy for next group
$result = 0;
}
elseif($group == 1) {
//Just take the highest value
$result = $item[0];
}
else {
//check this item with following groups
$result = $item[0] + $this->KS_Solver($n - $count, $c - $item[1]);
}
if($result == $item[0] && $group != 1) {
//No solution with the following sets, so don't use this item.
$result = 0;
}
if($result > $bestVal) {
//Best item so far
$bestVal = $result;
}
//memo the results
$this->memo2[$n-$k][$c] = $result;
$k--;
}
$result = $bestVal;
}
//memo and return
$this->memo1[$group][$c] = $result;
return $result;
}
}
new KS_Solve();
?>