# xkcd 287

I’m not sure what this problem is called – I’m going to call it "multicombination sum" – but I don’t doubt that it is NP-complete, as it’s a variety of knapsack problem in which the values of the items are the same as their weight.

Below are three methods of solving it: a brute force method, using backtracking, and using dynamic programming.

## Brute force method

The brute force method is just to construct all of the possible orders that might total \$15.05.
The combinatorial algorithm we want is combinations with duplicates, or multicombinations.
Since 3 of the most expensive appetizer – SAMPLER PLATE – exceeds the target, and 7 of the cheapest appetizer – MIXED FRUIT – equals the target (so that’s one of the solutions), we want to iterate over all multicombinations with k ranging from 3 to 7.

unsigned int multiset_sum(const unsigned int *multiset, const unsigned int *values, unsigned int k)
{
unsigned int i;
unsigned int sum = 0;
for (i = 0; i < k; i++) {
sum += values[multiset[i]];
}
return sum;
}

typedef void (*multiset1fn)(const unsigned int *, unsigned int);

void multicombination_sum(const unsigned int *items, size_t len, unsigned int target,
multiset1fn fun)
{
unsigned int first = target / array_max(items, len);
unsigned int last = target / array_min(items, len);
unsigned int *multiset = calloc(last + 1, sizeof(unsigned int));
unsigned int k;
if (!multiset) {
return;
}
for (k = first; k <= last; k++) {
do {
if (multiset_sum(multiset, items, k) == target) {
fun(multiset, k);
}
} while (next_multicombination(multiset, len, k));
}
free(multiset);
}

void order_print(const unsigned int *numbers, unsigned int k)
{
const char *appetizers[] = {"MIXED FRUIT", "FRENCH FRIES", "SIDE SALAD",
"HOT WINGS", "MOZARELLA STICKS", "SAMPLER PLATE"};
unsigned int i, item, count;
for (i = 0; i < k; i++) {
if (i == 0 || numbers[i] != item) {
if (i > 0) {
printf("%s (x%d) ", appetizers[item], count);
}
count = 1;
item = numbers[i];
}
else {
count++;
}
}
printf("%s (x%d)\n", appetizers[item], count);
}

int main(void)
{
unsigned int prices[] = {215, 275, 335, 355, 420, 580};
const size_t n = sizeof(prices) / sizeof(prices[0]);
const unsigned int target = 1505;
multicombination_sum(prices, n, target, (multiset1fn)order_print);

return 0;
}


Output:

MIXED FRUIT (x1) HOT WINGS (x2) SAMPLER PLATE (x1)
MIXED FRUIT (x7)


This took 1709 iterations to come up with the answer.

## Backtracking

We can drastically reduce the search space by building the orders up one item at a time, and backtracking if the target is exceeded.


typedef void(*multiset2fn)(unsigned int *, const unsigned int *, size_t);

static void multicombination_sum_recursive(int i, unsigned int *combination,
const unsigned int *items, size_t len, unsigned int target, multiset2fn fun,
unsigned int sum)
{
if (i == (int)len - 1) {
if (sum == target) {
fun(combination, items, i);
}
}
else  {
unsigned int quantity;
unsigned int max_quantity = (target - sum) / items[i + 1];
for (quantity = 0; quantity  <= max_quantity; quantity++) {
combination[i + 1] = quantity;
multicombination_sum_recursive(i + 1, combination, items, len, target, fun,
sum + quantity * items[i + 1]);
}
}
}

void multicombination_sum(const unsigned int *items, size_t len, unsigned int target,
multiset2fn fun)
{
unsigned int *combination = malloc(len * sizeof(unsigned int));
multicombination_sum_recursive(-1, combination, items, len, target, fun, 0);
free(combination);
}

void order_print(const unsigned int *combination, const unsigned int *items, size_t len)
{
const char *appetizers[] = {"MIXED FRUIT", "FRENCH FRIES", "SIDE SALAD",
"HOT WINGS", "MOZARELLA STICKS", "SAMPLER PLATE"};
unsigned int i;
for (i = 0; i <= len; i++) {
if (combination[i] > 0) {
printf("%s (x%d) ", appetizers[i], combination[i]);
}
}
putchar('\n');
}

int main(void)
{
unsigned int prices[] = {215, 275, 335, 355, 420, 580};
const unsigned int len = sizeof(prices) / sizeof(unsigned int);
const unsigned int target = 1505;
multicombination_sum(prices, len, target, (multiset2fn)order_print);
return 0;
}


Output:

MIXED FRUIT (x1) HOT WINGS (x2) SAMPLER PLATE (x1)
MIXED FRUIT (x7)


This took just 211 iterations.

## Dynamic Programming

As I said at the beginning, this problem is a special case of the knapsack problem in which the values of the items are the same as their weight. This means that we can use the classic dynamic programming algorithm for knapsack to solve it. The algorithm works by calculating the most profitable knapsack for each capacity up to the target capacity.

Here is an implementation of the algorithm:

struct knapsack {
unsigned int profit;
struct knapsack *prev;
};
typedef struct knapsack knapsack;

/* Find the minimum weight item with this profit */
int min_weight_item(unsigned int profit, const unsigned int *weights, const unsigned int *profits,
size_t len)
{
int item = -1;
unsigned int i;
for (i = 0; i < len; i++) {
if (profits[i] == profit) {
if (item == -1 || weights[i] < weights[item]) {
item = i;
}
}
}
return item;
}

unsigned int unbounded_knapsack(unsigned int capacity, unsigned int *weights,
unsigned int *profits, unsigned int *counts, size_t len)
{
knapsack *z = malloc((capacity + 1) * sizeof(knapsack));
unsigned int c, i;
unsigned int solution, profit;
z[0].profit = 0;
z[0].prev = NULL;
knapsack *current;
/* Fill in the array */
for (c = 1; c <= capacity; c++) {
z.profit = z.profit;
z.prev = &(z);
for (i = 0; i < len; i++) {
if (weights[i] <= c) {
knapsack *prev = z + (c - weights[i]);
if (prev->profit + profits[i] > z.profit) {
z.profit = prev->profit + profits[i];
z.prev = prev;
}
}
}
}
/* Read back the best solution */
for (profit = z[capacity].profit, current = z[capacity].prev;
current != NULL;
profit = current->profit, current = current->prev) {
counts[min_weight_item(profit - current->profit, weights, profits, len)]++;

}
solution = z[capacity].profit;
free(z);
return solution;
}


We just need to use this algorithm and pass the prices of the menu items for both weights and profits:

int main(void)
{
unsigned int values[] = {215, 275, 335, 355, 420, 580};
const size_t len = sizeof(values) / sizeof(values[0]);
unsigned int counts[6] = {0};
const unsigned int target = 1505;
unbounded_knapsack(target, values, values, counts, len);
order_print(counts, len);
return 0;
}


This produces one of the solutions:

MIXED FRUIT (x7)


We could modify the algorithm to produce all of them.