Solve Multiple Choice Knapsack (MCKP) With Dynamic Programming?

Question

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:

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);
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. 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?

Answer 1

The c++ implementation looks ok.

Your values and weights which are 1 dimensional array in your current PHP implementation will become 2 dimensional.

So for example,

values[i][j] will be value of j th item in class i. Similarly in case of weights[i][j]. You will be taking only one item for each class i and move forward while maximizing the condition.

The c++ implementation also does an optimization in memo. It only keeps 2 arrays of size respecting the max_weight condition, which are current and previous states. This is because you only need these 2 states at a time to compute present state.

Answers to your doubts:

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);

This won't work because there could be some item in class k+1 where you take a optimal value and to respect constraint you need to take a suboptimal value for class k. So sorting and picking the best won't work when the constraint is hit. If the constraint is not hit you can always pick the best value with best weight.

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.

Yes you are on the right track here. You will assume that you had already solved for first k classes. Now you will try extending using the values of k+1 class respecting the weight constraint.

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);
}

In the above c++ snippet, the first loop iterates on class, the second loop iterates on values of class and the third loop extends the current state current using the previous state last and only 1 item j with class i at a time. Since you are only using previous state last and 1 item of the current class to extend and maximize, you are following the constraint.

Time complexity:

O( total_items x max_weight) which is equivalent to O( class x max_number_of_items_in_a_class x max_weight)