Tag Archives: Knapsack

0-1 Knapsack using dynamic programming in C

Recall that the 0-1 Knapsack problem is to fill a knapsack of given capacity with items of given weights and values in order to maximise the value of the knapsack’s contents. This can be solved in pseudo-polynomial time using dynamic programming.

This is another table-filling algorithm. The rows of the table represent items, and the columns are weights of the knapsack.

struct knapsack_entry {
    unsigned int value;
    unsigned int item;
    struct knapsack_entry *prev;
};
typedef struct knapsack_entry knapsack_entry;
 
unsigned int knapsack(const unsigned int *weights, const unsigned int *values, size_t n,
        unsigned int capacity, unsigned int **solution)
{
    unsigned int i, j;
    knapsack_entry **table;
    unsigned int result;
    knapsack_entry *head;

    /* Allocate the table */ 
    table = malloc((n + 1) * sizeof(knapsack_entry *));
    for (i = 0; i <= n; i++) {
        table[i] = malloc((capacity + 1) * sizeof(knapsack_entry));
    }

    /* Calculate the values and build chains */ 
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= capacity; j++) {
            if (i == 0 || j == 0) {
                /* Initialising the first row or column */
                table[i][j].value = 0;
                table[i][j].item = 0;
                table[i][j].prev = NULL;
            }
            else if (weights[i - 1] <= j) {
                /* Can add item */
                if (values[i - 1] + table[i - 1][j - weights[i - 1]].value 
                        > table[i - 1][j].value) {
                    /* Add item */
                    table[i][j].value = values[i - 1] + table[i - 1][j - weights[i - 1]].value;
                    table[i][j].item = i - 1;
                    table[i][j].prev = &table[i - 1][j - weights[i - 1]];
                }
                else {
                    /* Don't add item */
                    table[i][j].value = table[i - 1][j].value;
                    table[i][j].item = table[i - 1][j].item;
                    table[i][j].prev = table[i - 1][j].prev;
                }
            }
            else {
                /* Don't add item */
                table[i][j].value = table[i - 1][j].value;
                table[i][j].item = table[i - 1][j].item;
                table[i][j].prev = table[i - 1][j].prev;
            }
        }
    }

    /* Read back the solution */
    *solution = calloc(n, sizeof(unsigned int));
    for (i = 0, head = &table[n][capacity];
            head->prev != NULL;
            head = head->prev, i++) {
        (*solution)[head->item] = 1;
    }
 
    result = table[n][capacity].value;
    for (i = 0; i <= n; i++) {
        free(table[i]);
    }
    free(table);
    return result;
}

Here is an example program:

int main(void)
{
    unsigned int weights[] = {2, 3, 4, 5, 9};
    unsigned int values[] = {3, 4, 5, 8, 10};
    const unsigned int capacity = 20;
    const size_t n = sizeof(weights) / sizeof(weights[0]);
    unsigned int *solution;
    unsigned int value = knapsack(weights, values, n, capacity, &solution);
    unsigned int i;
    printf("Value: %u\n", value);
    printf("Items in knapsack:\n");
    for (i = 0; i < n; i++) {
        if (solution[i]) {
            printf("Item %u with weight %u and value %u\n", i, weights[i], values[i]);
        }
    }
    free(solution);
    return 0;
}

The output:

Value: 26
Items in knapsack:
Item 0 with weight 2 and value 3
Item 2 with weight 4 and value 5
Item 3 with weight 5 and value 8
Item 4 with weight 9 and value 10

0-1 Knapsack using backtracking in C

In the 0-1 Knapsack problem, we are given a set of items with individual weights and profits and a container of fixed capacity (the knapsack), and are required to compute a loading of the knapsack with items such that the total profit is maximised. We only have 1 of each item, so there is either 0 or 1 of each item in in the knapsack, hence the 0-1 in the name of the problem.

The 0-1 knapsack problem is NP-hard, but can be solved quite efficiently using backtracking. Below is a backtracking implementation in C. The function knapsack() takes arrays of weights, and profits, their size, the capacity, and the address of a pointer through which the solution array is returned. It returns the profit of the best knapsack. The profit density of each item (weight / profit) is first calculated, and the knapsack is filled in order of decreasing profit density. A bounding function is used to determine the upper bound on the profit achievable with the current knapsack so as to reduce the search space.

#include <stdlib.h>
#include <string.h>

/* A knapsack item */
typedef struct {
    unsigned int id;
    double weight;
    double profit;
    double profit_density;
} item;

/* Compare items by lesser profit density */
static int compare_items(const item *item1, const item *item2)
{
    if (item1->profit_density > item2->profit_density) {
        return -1;
    }
    if (item1->profit_density < item2->profit_density) {
        return 1;
    }
    return 0;
}

/* Bounding function */
static double profit_bound(const item *items, size_t n, double capacity,
        double current_weight, double current_profit,
        unsigned int level)
{
    double remaining_capacity = capacity - current_weight;
    double bound = current_profit;
    unsigned int lvl = level;
    /* Fill in order of decreasing profit density */
    while (lvl < n &&
        items[lvl].weight <= remaining_capacity) 
    {
        remaining_capacity -= items[lvl].weight;
        bound += items[lvl].profit;
        lvl++;
    }
    /* Pretend we can take a fraction of the next object */
    if (lvl < n) {
        bound += items[lvl].profit_density
            * remaining_capacity;
    }
    return bound;
}

static void knapsack_recursive(const item *items, size_t n, double capacity,
        unsigned int *current_knapsack, double *current_weight, double *current_profit,
        unsigned int *max_knapsack, double *max_profit, unsigned int level)
{   
    if (level == n) {
        /* Found a new max knapsack */
        *max_profit = *current_profit;
        memcpy(max_knapsack, current_knapsack, n * sizeof(unsigned int));
        return;
    }
    if (*current_weight + items[level].weight <= capacity)
    {   /* Try adding this item */
        *current_weight += items[level].weight;
        *current_profit += items[level].profit;
        current_knapsack[items[level].id] = 1;
        knapsack_recursive(items, n, capacity, current_knapsack, current_weight, 
                current_profit, max_knapsack, max_profit, level + 1);
        *current_weight -= items[level].weight;
        *current_profit -= items[level].profit;
        current_knapsack[items[level].id] = 0;
    }
    if (profit_bound(items, n, capacity, *current_weight, 
                *current_profit, level + 1) > *max_profit) {
        /* Still promising */
        knapsack_recursive(items, n, capacity, current_knapsack, current_weight, 
                current_profit, max_knapsack, max_profit, level + 1);
    }
}

double knapsack(const double *weights, const double *profits, 
        size_t n, double capacity, unsigned int **max_knapsack)
{
    double current_weight = 0.0;
    double current_profit = 0.0;
    double max_profit = 0.0;
    unsigned int i;
    item *items  = malloc(n * sizeof(item));
    unsigned int *current_knapsack = calloc(n, sizeof(unsigned int));
    *max_knapsack = malloc(n * sizeof(unsigned int));
    if (!(items && current_knapsack && *max_knapsack)) {
        free(items);
        free(current_knapsack);
        free(*max_knapsack);
        *max_knapsack = NULL;
        return 0;
    }
    /* Populate the array of items */
    for (i = 0; i < n; i++) {
        items[i].id = i;
        items[i].weight = weights[i];
        items[i].profit = profits[i];
        items[i].profit_density = profits[i] / weights[i];
    }
    /* Sort into decreasing density order */
    qsort(items, n, sizeof(item),
            (int (*)(const void *, const void *))compare_items);
    knapsack_recursive(items, n, capacity, current_knapsack, &current_weight,
            &current_profit, *max_knapsack, &max_profit, 0);
    free(items);
    free(current_knapsack);
    return max_profit;
}

Here is an example program:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    double weights[] = {3, 5, 2, 1};
    double profits[] = {9, 10, 7, 4};
    const size_t n = sizeof(profits) / sizeof(profits[0]);
    const double capacity = 7;
    unsigned int *max_knapsack;
    double max_profit = knapsack(weights, profits, n, capacity, &max_knapsack);
    unsigned int i;
    printf("Profit: %.2f\n", max_profit);
    printf("Knapsack contains:\n");
    for (i = 0; i < n; i++) {
        if (max_knapsack[i] == 1) {
            printf("Item %u with weight %.2f and profit %.2f\n", i, weights[i], profits[i]); 
        }
    }
    free(max_knapsack);
    return 0;
}

The output:

Profit: 20.00
Knapsack contains:
Item 0 with weight 3.00 and profit 9.00
Item 2 with weight 2.00 and profit 7.00
Item 3 with weight 1.00 and profit 4.00

Value-Independent Knapsack Problem using backtracking in C

In another post I described a backtracking algorithm for the Subset-Sum Problem, in which the aim is to find a subset of a set of weights that sums to a given weight. A related problem, which is sometimes called Subset-Sum but is also called Value-Independent Knapsack, is to find a subset of the set of weights that is the maximum weight less than or equal to the given weight, rather than the exact weight.

This problem can be thought of as a 0-1 knapsack problem in which the weights are equal to the values for all items. Like 0-1 knapsack, the problem is NP-hard, but a backtracking algorithm can produce an exact solution quite efficiently. This is a backtracking algorithm for Value Independent Knapsack in C. The function subset_sum() takes an array of weights and its size, a capacity, and an out parameter for the solution array, and returns the weight of the best set found.

static void subset_sum_recursive(const unsigned int *weights, size_t n, unsigned int capacity, 
        unsigned int *current_set, unsigned int *current_weight, unsigned int *max_set, 
        unsigned int *max_weight, unsigned int *remaining_weight, unsigned int level)
{
    if (level == n) {
        /* Found a new best set */
        *max_weight = *current_weight;
        memcpy(max_set, current_set, n * sizeof(unsigned int));
        return;
    }
    *remaining_weight -= weights[level];
    if (*current_weight + weights[level] <= capacity) {
        /* Try solutions that include this item */
        *current_weight += weights[level];
        current_set[level] = 1;
        subset_sum_recursive(weights, n, capacity, current_set, current_weight, 
                max_set, max_weight, remaining_weight, level + 1);
        *current_weight -= weights[level];
        current_set[level] = 0;
    }
    if (*current_weight + *remaining_weight > *max_weight) { 
        /* Still promising */
        subset_sum_recursive(weights, n, capacity, current_set, current_weight, 
                max_set, max_weight, remaining_weight, level + 1);
    }
    *remaining_weight += weights[level];
}

static unsigned int sum(const unsigned int *numbers, size_t len)
{
    unsigned int total = 0;
    unsigned int i;
    for (i = 0; i < len; i++) {
        total += numbers[i];
    }
    return total;
}

static unsigned int subset_sum(const unsigned int *weights, size_t n, unsigned int capacity,
        unsigned int **max_set)
{
    unsigned int current_weight = 0;
    unsigned int max_weight = 0;
    unsigned int remaining_weight = sum(weights, n);
    unsigned int *current_set = calloc(n, sizeof(unsigned int));
    *max_set = malloc(n * sizeof(unsigned int));
    if (current_set == NULL || *max_set == NULL) {
        free(current_set);
        free(*max_set);
        return 0;
    }
    subset_sum_recursive(weights, n, capacity, current_set, &current_weight, *max_set,
           &max_weight, &remaining_weight, 0);
    free(current_set);
    return max_weight;
}

Here is an example program. It prints the maximum weight found and the elements of the set:

int main(void)
{
    unsigned int weights[] = {8, 6, 2, 3};
    const size_t n = sizeof(weights) / sizeof(weights[0]);
    const unsigned int capacity = 12;
    unsigned int *set;
    unsigned int weight = subset_sum(weights, n, capacity, &set);
    unsigned int i;
    printf("%u\n", weight);
    for (i = 0; i < n; i++) {
        if (set[i]) {
            printf("%u ", weights[i]);
        }
    }
    putchar('\n');
    free(set);
    return 0;
}

The output:

11
8 3

Fractional Knapsack in C

The fractional knapsack problem is to fill a knapsack of given capacity with unique items of a given weight and value so as to maximise the value of the knapsack, with breaking items up being permitted. This last relaxation of the usual conditions means that we can use a greedy algorithm to solve the problem:

  1. Sort the items in decreasing order of value / weight
  2. Take as much as you can of each item until the knapsack is at capacity

Only the last item can need to be broken up because the sorting by value / weight guarantees that the current item is the optimum one to take, so we should take as much as it as we can, which until the knapsack cannot contain it, will be the whole item. When the knapsack cannot contain it we enough of it to fill the remaining capacity and so are at the last item.

This is the algorithm in C. I have assumed that value / weight is always a whole number for simplicity, but one could easily modify it for continuous values.

typedef struct {
    unsigned int value;
    unsigned int weight;
    unsigned int index;
} item;

/* Compare items by greater value / weight */
int compare_items(const item *item1, const item *item2)
{
    unsigned int vw1 = item1->value / item1->weight;
    unsigned int vw2 = item2->value / item2->weight;
    if (vw1 > vw2) {
        return -1;
    }
    else if (vw1 == vw2) {
        return 0;
    }
    return 1;
}

unsigned int fractional_knapsack(const unsigned int *values, const unsigned int *weights, 
        unsigned int *knapsack, size_t len, unsigned int capacity)
{
    unsigned int i;
    unsigned int remaining = capacity;
    unsigned int value = 0;
    item *items;
   
    items = malloc(len * sizeof(item));
    if (items == NULL) {
        return 0;
    }
    for (i = 0; i < len; i++) {
        items[i].value = values[i];
        items[i].weight = weights[i];
        items[i].index = i;
    }
    /* Sort items in descending order by value / weight */
    qsort(items, len, sizeof(item), (int(*)(const void *, const void *))compare_items);
    for (i = 0; i < len && remaining > 0; i++) {
        if (items[i].weight < remaining) {
            /* Take all of this item */
            value += items[i].value;
            knapsack[items[i].index] = items[i].weight;
            remaining -= items[i].weight;
        }
        else {
            /* Take a fraction of this item */
            value += (items[i].value * remaining) / items[i].weight;
            knapsack[items[i].index] = remaining;
            remaining = 0;
        }
    }
    free(items);

    return value;
}

Example program:

void print_knapsack(const unsigned int *knapsack, const unsigned int * values,
        const unsigned int *weights, size_t len)
{
    unsigned int i;
    for (i = 0; i < len; i++) {
        if (knapsack[i] > 0) {
           if (knapsack[i] == weights[i]) {
               printf("1 ");
           }
           else {
               printf("%u/%u ", knapsack[i], weights[i]);
           }
           printf("of item %u (weight %u value %u)\n", i, weights[i], values[i]);
        }
    }
}

int main(void)
{
    unsigned int values[] = { 200, 240, 140, 150 };
    unsigned int weights[] = { 1, 3, 2, 5 };
    const size_t len = sizeof(values) / sizeof(unsigned int);
    unsigned int *knapsack;
    const unsigned int capacity = 5;
    unsigned int value;
   
    knapsack = calloc(len, sizeof(unsigned int));
    value = fractional_knapsack(values, weights, knapsack, len, capacity);
    printf("Value is %d\n", value);
    print_knapsack(knapsack, values, weights, len);
    free(knapsack);

    return 0;
}

Output:

Value is 510
1 of item 0 (weight 1 value 200)
1 of item 1 (weight 3 value 240)
1/2 of item 2 (weight 2 value 140)

Unbounded Knapsack using dynamic programming in C

The unbounded knapsack problem is to try to fill a knapsack of a given capacity with items of given weight and value in such a way as to maximise the value of the knapsack. There is no limit on the number of instances of each item, hence the “unbounded” label. The decision problem of whether the knapsack can be filled to greater than or equal to a value is NP-complete. The maximisation problem can be solved in pseudo-polynomial time using dynamic programming.

The algorithm works by filling an array of 0, …, the capacity of the knapsack from the bottom up with the value most valuable knapsack for each capacity. In order to work out at each capacity what the most profitable knapsack is, it considers each item in turn and finds out what the value of the knapsack would be if this was the last item added. This value is the value of the earlier knapsack that is lighter by the weight of the current item, plus the value of the current item. Since the knapsack values are calculated from lower to higher capacities, the value of this earlier, lighter knapsack can always be found without needing to recompute it. Once each of the items has been considered as the most recent addition, the one that gives rise to the most valuable knapsack is added, and this value is recorded in the current cell of the array. The algorithm then proceeds to the next cell of the array. When the algorithm reaches the top of the array, and fills that cell in, it has found the most valuable knapsack for the specified capacity.

There is an implicit link between each knapsack in the array and the previous lighter knapsack from which it was derived by adding an item. These links form multiple chains through the array. The chain that begins at the top cell is the one that traces the path of additions that have led to the most profitable knapsack. In order to realise this link, the array cells contain pointers to the earlier knapsack from which they were constructed, and these pointers are set as the algorithm progresses. Once the array is full, the values of the items can be retrieved by following this linked list of pointers.

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) {
                /* prev is the best knapsack without adding this item */
                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;
}

An example program:

static void print_knapsack(const unsigned int *counts, const unsigned int *profits, size_t len)
{
	unsigned int i;
    for (i = 0; i < len; i++) {
        if (counts[i] > 0) {
            printf("%d x %d\n", counts[i], profits[i]);
        }
    }
}

int main(void)
{
    unsigned int weights[] = {4, 3, 5, 7, 11};
    unsigned int profits[] = {5, 3, 6, 2, 7};
    unsigned int counts[5] = {0};
    const size_t len = sizeof(weights) / sizeof(unsigned int);
    const unsigned int capacity = 17; 
    printf("The maximum profit is %u\n", 
            unbounded_knapsack(capacity, weights, profits, counts, len));
    print_knapsack(counts, profits, len);
    return 0;
}

Output:

The maximum profit is 21
3 x 5
1 x 6

xkcd 287

General solutions get you a 50% tip

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.