使用动态规划解决多项选择背包 (MCKP)? [英] Solve Multiple Choice Knapsack (MCKP) With Dynamic Programming?
本文介绍了使用动态规划解决多项选择背包 (MCKP)?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
示例数据
对于这个问题，让我们假设以下项目:
- 物品:苹果、香蕉、胡萝卜、牛排、洋葱
- 值:2、2、4、5、3
- 权重:3、1、3、4、2
- 最大重量:7
目标:
MCKP 是一种背包问题，附加约束是[T]他的项目被细分为k个类别... 并且必须从每个类别中提取一个项目"
我已经编写了使用递归调用和记忆化的动态编程来解决 0/1 KS 问题的代码.我的问题是是否可以将此约束添加到我当前的解决方案中?假设我的课程是水果、蔬菜、肉类(来自示例)，我需要包含每种类型的 1 个.类也可以是类型 1、2、3.
另外，我认为这可以通过线性规划和求解器来解决，但如果可能的话，我想了解这里的答案.
当前代码:
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];休息;}}}//打印出选择的项目和最大值print("<pre>".print_r($picked,true)."</pre>");回声 $KSResult;//解决KS问题的递归公式//$n = 要检查的项目数//$c = 袋子的总容量功能 KSTest($n, $c, &$value, &$weight) {全球$看到;if(isset($seen[$n][$c])) {//我们以前见过这个子问题返回 $seen[$n][$c];}if($n === 0 || $c === 0){//没有更多的项目要检查或没有更多的容量$结果= 0;}elseif($weight[$n] > $c) {//这个项目太重了，没有这个就检查下一个项目$result = KSTest($n-1, $c, $value, $weight);}别的 {//取保留或不保留项目的较高结果$tempVal1 = KSTest($n-1, $c, $value, $weight);$tempVal2 = $value[$n] + KSTest($n-1, $c-$weight[$n], $value, $weight);if($tempVal2 >= $tempVal1) {$result = $tempVal2;//有些条件可以放在这里?否则使用 max()}别的 {$result = $tempVal1;}}//记录结果并返回$seen[$n][$c] = $result;返回 $result;}?>我尝试过的:
- 我的第一个想法是添加一个class(k)数组，通过class(k)对items进行排序，当我们选择选择和下一个item相同的item时，检查是否最好保持当前项目或没有下一个项目的项目.看起来很有希望，但在检查了几个项目后就崩溃了.像这样的东西:$tempVal3 = $value[$n] + KSTest($n-2, $c-$weight[$n]);max($tempVal2, $tempVal3);
- 另一个想法是，在函数调用中，我可以为每个类类型调用一个循环，并一次只用该类型的 1 个项目 + 其余值来解决 KS.这肯定会做出一些假设，因为例如，集合 1 的结果可能仍然假设集合 2 的倍数.
这看起来是等式(如果你是擅长阅读所有这些符号?) :) 和 C++ 实现?但我真的看不到类约束在哪里发生?
解决方案
这是我的 PHP 解决方案.我尝试以易于理解的方式对代码进行注释.
更新:我更新了代码，因为旧脚本给出的结果不可靠.这更干净，并且已经过全面测试.关键要点是我使用了两个备忘录数组，一个在组级别以加快执行速度，另一个在项目级别以重建结果.我发现任何跟踪正在选择的项目的尝试都是不可靠的，而且效率低得多.此外， isset() 而不是 if($var) 对于检查备忘录数组是必不可少的，因为以前的结果可能是 0 ;)
KS_Items = array(数组(2, 3, 1, 1),数组(2, 1, 1, 2),数组(4, 3, 2, 3),数组(5, 4, 2, 4),数组(3, 2, 3, 5));$this->maxWeight = 7;$this->maxItems = 5;$this->KS_Wrapper();}公共函数 KS_Wrapper() {$start_time = microtime(true);//在前面放一个虚拟零，以便以后更容易.array_unshift($this->KS_Items, array(0, 0, 0, 0));//调用我们的背包求解器$this->maxValue = $this->KS_Solver($this->maxItems, $this->maxWeight);//从我们的备忘录数组中重新创建决策表以确定选择了哪些项目//ksort($this->memo2);//用于调试for($i=$this->maxItems;$i>0;$i--){//ksort($this->memo2[$i]);//用于调试for($j=$this->maxWeight;$j>0;$j--){if($this->maxValue == 0) {打破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];休息;}}}//打印出选择的项目和值.(实施正确的视图或返回！)echo "";echo "结果:<br>";回声值:".$this->finalValue ."<br>";回声重量:".$this->finalWeight ."<br>";echo "项目在 KS:" 中.$this->finalItems ."<br>";回声选定的组:".$this->finalGroups ."<br><br>";$end_time = microtime(true);$execution_time = ($end_time - $start_time);回声结果".sprintf('%f', $execution_time) ." 执行秒数
";}/*** 解决MCKS问题的递归函数* $n = 要检查的项目数* $c = KS 的总容量**/公共函数 KS_Solver($n, $c) {$group = $this->KS_Items[$n][2];$groupItems = array();$count = 0;$结果= 0;$bestVal = 0;if(isset($this->memo1[$group][$c])){$result = $this->memo1[$group][$c];}别的 {//对这个组的项目进行排序foreach($this->KS_Items as $item) {if($item[2] == $group) {$groupItems[] = $item;$count++;}}//$k 调整item memoization的索引$k = $count - 1;//求每个item+其他组item的结果foreach($groupItems 作为 $item) {if($item[1] > $c) {//太重$结果= 0;}elseif($item[1] >= $c && $group != 1) {//对于下一组来说太重了$结果= 0;}elseif($group == 1) {//取最高值$result = $item[0];}别的 {//使用以下组检查此项$result = $item[0] + $this->KS_Solver($n - $count, $c - $item[1]);}if($result == $item[0] && $group != 1) {//以下几套无解，故勿用此项.$结果= 0;}if($result > $bestVal) {//目前最好的项目$bestVal = $result;}//记录结果$this->memo2[$n-$k][$c] = $result;$k--;}$result = $bestVal;}//备忘录并返回$this->memo1[$group][$c] = $result;返回 $result;}}新 KS_Solve();?>Example Data
For this question, let's assume the following items:
- Items: Apple, Banana, Carrot, Steak, Onion
- Values: 2, 2, 4, 5, 3
- Weights: 3, 1, 3, 4, 2
- Max Weight: 7
Objective:
The MCKP is a type of Knapsack Problem with the additional constraint that "[T]he items are subdivided into k classes... and exactly one item must be taken from each class"
I have written the code to solve the 0/1 KS problem with dynamic programming using recursive calls and memoization. My question is whether it is possible to add this constraint to my current solution? Say my classes are Fruit, Vegetables, Meat (from the example), I would need to include 1 of each type. The classes could just as well be type 1, 2, 3.
Also, I think this can be solved with linear programming and a solver, but if possible, I'd like to understand the answer here.
Current Code:
<?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;
}
?>
What I've Tried:
- 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);
- 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. This will definitely be making some assumptions thought because the results of set 1 might still be assuming multiples of set 2, for example.
This looks to be the equation (If you are good at reading all those symbols?) :) and a C++ implementation? but I can't really see where the class constraint is happening?
解决方案
This is my PHP solution. I've tried to comment the code in a way that it's easy to follow.
Update: I updated the code because the old script was giving unreliable results. This is cleaner and has been thoroughly tested. Key takeaways are that I use two memo arrays, one at the group level to speed up execution and one at the item level to reconstruct the results. I found any attempts to track which items are being chosen as you go are unreliable and much less efficient. Also, isset() instead of if($var) is essential for checking the memo array because the previous results might have been 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();
?>
这篇关于使用动态规划解决多项选择背包 (MCKP)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
