php - 用动态规划解决多项选择背包 (MCKP)？

Question

示例数据

对于这个问题，让我们假设以下项目:

• 项目:苹果、香蕉、胡萝卜、牛排、洋葱
• 值:2、2、4、5、3
• 权重:3、1、3、4、2
• 最大体重:7

目标:

MCKP 是一种 Knapsack Problem附加约束是“[T]他的项目被分割为k类......并且必须从每个类中取出一个项目”

我已经编写了使用递归调用和记忆化的动态编程来解决 0/1 KS 问题的代码。我的问题是是否可以将此约束添加到我当前的解决方案中？假设我的类(class)是水果、蔬菜、肉类(来自示例)，我需要包括每种类型的 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;
}
?>

我尝试过的:

1. 我的第一个想法是添加一个类(k)数组，通过类(k)对项目进行排序，当我们选择选择一个与下一个项目相同的项目时，检查是否保留当前的更好项目或没有下一项的项目。看起来很有希望，但在检查了几项之后就崩溃了。是这样的:$tempVal3 = $value[$n] + KSTest($n-2, $c-$weight[$n]);最大值( $tempVal2, $tempVal3);
2. 另一个想法是，在函数调用时，我可以为每个类类型调用一个循环，并一次仅使用该类型的 1 个项目 + 其余值来求解 KS。这肯定会做出一些假设，因为第 1 组的结果可能仍然假设第 2 组的倍数，例如。

This looks to be the equation (如果您擅长阅读所有这些符号？):) 和 C++ 实现？但我真的看不出类约束在哪里发生？

Answer 1

C++ 实现看起来不错。

在您当前的 PHP 实现中，您的值和权重是一维数组，将变为二维。

例如，

values[i][j]将是 j 的值(value)类里面的第一个项目 i .同样在 weights[i][j] 的情况下.每堂课你将只拿一件元素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);

这是行不通的，因为 k+1 类中可能有一些项目，您在其中取了最佳值，并且为了遵守约束，您需要为 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 个类。现在，您将尝试根据权重约束使用 k+1 类的值进行扩展。

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++ 代码片段中，第一个循环迭代类，第二个循环迭代类的值，第三个循环扩展当前状态 current使用之前的状态 last并且只有 1 件 j与类 i一次。由于您只使用以前的状态 last和要扩展和最大化的当前类的 1 个项目，您遵循约束。

时间复杂度:

O( total_items x max_weight) 相当于 O( class x max_number_of_items_in_a_class x最大重量)