XKCD’s Knapsack Problem in Minizinc

Here’s my implementation of the knapsack problem described in the XKCD comic (pictured below) using the Minizinc constraint programming language.

http://xkcd.com/287/

 % XKCD Knapsack Problem in Minizinc
 % Model created by Jess T
 %

int: maxPossibilities = 7;
int: numberOfAppetizers = 6;

% an array of floats is not supported, hence why i have used ints
array[1..numberOfAppetizers] of int: apps = [215, 275, 335, 355, 420, 580];
array[1..maxPossibilities] of var 0..580: finalArray;

constraint
    forall (i in 1..maxPossibilities) (
    finalArray[i] == 0 \/
    finalArray[i] == apps[1] \/
    finalArray[i] == apps[2] \/
    finalArray[i] == apps[3] \/
    finalArray[i] == apps[4] \/
    finalArray[i] == apps[5] \/
    finalArray[i] == apps[6]
);

constraint
    (sum(i in 1..maxPossibilities) (finalArray[i])) == 1505;

solve satisfy;

finalArray = [355, 215, 0, 0, 0, 355, 580]
or Hot Wings ($3.55) + Mixed Fruit ($2.15) + Hot Wings ($3.55) + Sampler Plate ($5.80) = $15.05.

~ by jessiespaghetti on 10th February, 2009.