示例数据
对于这个问题，让我们假设以下物品：
- 物品：苹果、香蕉、胡萝卜、牛排、洋葱
- 价值：2、2、4、5、3
- 重量：3、1、3、4、2
- 最大重量：7
目标：
MCKP是一种带有附加约束条件的背包问题，"[T]该问题将物品划分为k类...每个类别必须选择一个物品"。
我已经编写了使用递归调用和记忆化的动态规划来解决01背包问题的代码。我的问题是是否可以将此约束条件添加到当前的解决方案中？例如，如果我的类别是水果、蔬菜、肉类（从示例中），我需要包含每种类型的1个物品。这些类别也可以是类型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;
}
?>
我尝试过的方法：
- 我的第一个想法是添加一个类（k）数组，通过类（k）对项目进行排序，并在我们选择选择与下一个项目相同的项目时，检查是保留当前项目还是不包括下一个项目的项目更好。看起来很有希望，但是在检查了几个项目后就崩溃了。大致代码如下： $tempVal3 = $value[$n] + KSTest($n-2, $c-$weight[$n]); max( $tempVal2, $tempVal3);
- 另一个想法是，在函数调用时，我可以为每种类别调用一个循环，并仅解决该类型的每次选择1项 +其余值的KS问题。这肯定会做出一些假设，因为集合1的结果可能仍然假定集合2的倍数，例如。
这似乎是方程式（如果你擅长阅读所有这些符号？）:)和C ++实现？但我真的看不到类约束发生的地方？
else if和else语句的。你说得对，现在权重是一个二维数组，但可以按照你想要的方式实现它，以便能够访问特定类别的所有权重。 - Yonlif