Tag Archives: Dynamic Programming

Max subarray sum using dynamic programming in C

The maximum subarray problem is to find the subarray within an array of integers with the largest sum. There is a linear time dynamic programming algorithm for solving it invented by Joseph Kadane.

Here it is in C:

int max(int a, int b)
{
    return a > b ? a : b;
}

int max_subarray(int *array, size_t n)
{
    int max_ending_here = 0;
    int max_so_far = 0;
    unsigned int i;

    for (i = 0; i < n; i++) {
        max_ending_here = max(0, max_ending_here + array[i]);
        max_so_far = max(max_so_far, max_ending_here);
    }
    return max_so_far;
}

Example program:

int main(void)
{
    int array[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    const size_t n = sizeof(array) / sizeof(int);
    printf("Max subarray sum is %d\n", max_subarray(array, n));
    return 0;
}

Output:

6

Partition function using dynamic programming in C

A partition of an integer is a way of writing it as a sum of positive integers. For example, partitions of 5 are:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

The order of numbers in a partition doesn’t matter. The number of partitions of a number \(n\) is given by the partition function \(p(n)\).

The first few values of \(p(n)\) are 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, … (A000041).

The partition function can be computed using a dynamic programming table-filling algorithm. Here it is in C:

#include <stdlib.h>

unsigned int partition(unsigned int n)
{
    unsigned int i, j;
    unsigned int result;
    unsigned int **table;

    if (n == 0) {
        return 1;
    }
   
    table = malloc((n + 1) * sizeof(unsigned int *));
    for (i = 0; i <= n; i++) {
        table[i] = malloc((n + 1) * sizeof(unsigned int));
    }

    for (i = 0;i <= n; i++) {
        table[i][0]=0;
    }
    for (i = 1; i <= n; i++) {
        table[0][i] = 1;
    }

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (j > i) {
                table[i][j] = table[i][j - 1];
            }
            else {
                table[i][j] = table[i][j - 1] + table[i - j][j];
            }
        }
    }

    result = table[n][n];
    for (i = 0; i <= n; i++) {
        free(table[i]);
    }
    free(table);

    return result;
}

Example program:

#include <stdio.h>

int main(void) 
{
    unsigned int i;
    for (i = 0; i < 31; i++) {
        printf("%d\n",partition(i));
    }

    return 0;
}

Output:

1
1
2
3
5
7
11
15
22
30
42
56
77
101
135
176
231
297
385
490
627
792
1002
1255
1575
1958
2436
3010
3718
4565
5604

Shortest Common Supersequence using dynamic programming in C

The Shortest Common Supersequence (SCS) problem is to find the shortest sequence that is a supersequence of two or more sequences. It is closely related to the Longest Common Subsequence problem, in that the SCS of two strings is precisely their LCS, with those letters from each that are not in the LCS spliced into the string in their proper place relative to the SCS letters. For example, given the strings “pAqBrCs” and “wAxByCz”, their LCS is “ABC”, and an SCS is “wpAxqByrCzs”. Note that the order in which the letters occurring between the LCS letters is chosen from the two strings doesn’t matter, as long as the letters from each string are in the same order as they occur in it, so “pwAqxByrCsz” is also an SCS, and in general the SCS is not unique.

One way of computing an SCS is to use a dynamic programming algorithm similar to the Longest Common Subsequence one, but in which the letters occurring between the LCS letters are added to the solution. This is what I have implemented in C here. Rather than using pointers in the table to retrieve the solution as I have done in other DP algorithms, this time I have used enumerated values that indicate in which direction the next cell in the sequence is to be found – DOWN, RIGHT, or DIAG (diagonally down and to the right).

typedef enum  {
    DOWN,
    RIGHT,
    DIAG,
    STOP
} direction;
 
typedef struct {
	size_t len;
	char letter;
	direction dir;
} cell;
 
char *shortest_common_supersequence(const char *str1, const char *str2)
{
	size_t lstr1 = strlen(str1);
    size_t lstr2 = strlen(str2);
	cell **matrix;
    int i;
    int j;
    char *result;
    unsigned int r;

    matrix = malloc((lstr2 + 1) * sizeof(cell*));
    for (i = 0; i <= lstr2; i++) {
        matrix[i] = malloc((lstr1 + 1) * sizeof(cell));
    }
 
	for (i = 0; i < lstr2; i++) {
		matrix[i][lstr1].len = lstr2 - i;
        matrix[i][lstr1].letter = str2[i];
        matrix[i][lstr1].dir = DOWN;
    }
 
	for (j = 0; j < lstr1; j++) {
		matrix[lstr2][j].len = lstr1 - j;
        matrix[lstr2][j].letter = str1[j];
        matrix[lstr2][j].dir = RIGHT;
    }

	matrix[lstr2][lstr1].len = 0;
	matrix[lstr2][lstr1].letter = 0;
	matrix[lstr2][lstr1].dir = STOP;
 
	for (i = lstr2 - 1; i >= 0; i--) {
		for (j = lstr1 - 1; j >= 0; j--) {
			cell *pcell = &matrix[i][j];
			if (str2[i] == str1[j]) {
				pcell->dir = DIAG;
				pcell->letter = str1[j];
                pcell->len = matrix[i + 1][j + 1].len + 1;
			} 
            else if (matrix[i][j + 1].len < matrix[i + 1][j].len) {
				pcell->dir = RIGHT;
				pcell->letter = str1[j];
                pcell->len = matrix[i][j + 1].len + 1;
			}
            else {
				pcell->dir = DOWN;
				pcell->letter = str2[i];
                pcell->len = matrix[i + 1][j].len + 1;
			}
		}
	}
 
    result = malloc(matrix[0][0].len + 1);
    i = 0;
    j = 0;
    r = 0;
	while (i <= lstr2 && j <= lstr1) {
        result[r] = matrix[i][j].letter;
        r++;
        if (matrix[i][j].dir == DOWN) {
            i += 1;
        }
        else if (matrix[i][j].dir == RIGHT) {
            j += 1;
        }
        else {
            i += 1;
            j += 1;
        }
    }

    for (i = 0; i <= lstr2; i++) {
        free(matrix[i]);
    }
    free(matrix);
 
	return result;
}

Example program:

int main(void)
{
    char a[] = "pAqBrCs";
    char b[] = "wAxByCz";
    char *scs = shortest_common_supersequence(a, b);
    printf("%s\n", scs);
    free(scs);
    return 0;
}

Output:

wpAxqByrCzs

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

Longest Repeated Subsequence using dynamic programming in C

This problem is very like Longest Common Subsequence, except that we are looking for the longest subsequence occurring twice in the same string, rather than once in different strings. Once again, this is a dynamic programming solution using chains of pointers in the table to keep track of the subsequences under consideration.

struct lrs_entry {
    unsigned int score;
    char letter;
    struct lrs_entry *prev;
};
typedef struct lrs_entry lrs_entry;

unsigned int longest_repeated_subsequence(const char *str, char **result)
{
    const size_t len = strlen(str);
    lrs_entry **lrstab;
    unsigned int i, j;
    unsigned int max;
    lrs_entry *head;

    /* Allocate the table */ 
    lrstab = malloc((len + 1) * sizeof(lrs_entry *));
    for (i = 0; i <= len; i++) {
        lrstab[i] = malloc((len + 1) * sizeof(lrs_entry));
    }
 
    /* Calculate the scores and build the chains */
    for (i = 0; i <= len; i++) {
        for (j = 0; j <= len; j++) {
            if (i == 0 || j == 0) {
                /* Initialising the first row or column */
                lrstab[i][j].score = 0;
                lrstab[i][j].letter = 0;
                lrstab[i][j].prev = NULL;
            }
            else if (str[i - 1] == str[j - 1] && i != j) {
                /* Match */
                lrstab[i][j].score = lrstab[i - 1][j - 1].score + 1;
                lrstab[i][j].letter = str[i - 1];
                lrstab[i][j].prev = &lrstab[i - 1][j - 1];
            }                
            else {
                /* Mismatch */
                if (lrstab[i][j-1].score > lrstab[i-1][j].score) {
                    lrstab[i][j].score = lrstab[i][j-1].score;
                    lrstab[i][j].letter = lrstab[i][j-1].letter;
                    lrstab[i][j].prev = lrstab[i][j-1].prev;
                }
                else {
                    lrstab[i][j].score = lrstab[i - 1][j].score;
                    lrstab[i][j].letter = lrstab[i - 1][j].letter;
                    lrstab[i][j].prev = lrstab[i - 1][j].prev;
                }
            }
        }
    }
    
    max = lrstab[len][len].score;

    /* Allocate the output array and copy the LRS into it */
    *result = malloc(max + 1);
    for (i = max - 1, head = &lrstab[len][len];
            head->prev != NULL;
            head = head->prev, i--) {
        (*result)[i] = head->letter;
    }
    (*result)[max] = '\0';

    for (i = 0; i <= len; i++) {
        free(lrstab[i]);
    }
    free(lrstab);

    return max;
}

Example program:

int main()
{
    char str[] = "abcXdYeXZfgYhZijk";
    char *result;
    printf("Longest Repeated Subsequence: %u\n", longest_repeated_subsequence(str, &result));
    printf("%s\n", result);
    free(result);
    return 0;
}

Output:

Longest Repeated Subsequence: 3
XYZ

Longest Common Substring using dynamic programming in C

The Longest Common Substring problem is similar to Longest Common Subsequence, except that the subsequence must be made of adjacent characters – a substring. The dynamic programming algorithm is also very similar. For this one I have used chains of pointers in the table to retrieve the solution, as I did with Longest Increasing Subsequence,

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

struct lcs_entry {
    unsigned int score;
    char letter;
    struct lcs_entry* prev;
};
typedef struct lcs_entry lcs_entry;
 
unsigned int longest_common_substring(const char *str1, const char *str2,
        char **result)
{
    unsigned int i, j;
    unsigned int max = 0;
    lcs_entry *head;
    const size_t m = strlen(str1);
    const size_t n = strlen(str2);
    lcs_entry **lcstab;
   
    /* Allocate the table */
    lcstab = malloc((m + 1) * sizeof(lcs_entry*));
    for (i = 0; i < m + 1; i++) {
        lcstab[i] = malloc((n + 1) * sizeof(lcs_entry));
    }

    /* Calculate scores for each substring and build chains */ 
    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                lcstab[i][j].score = 0;
                lcstab[i][j].letter = 0;
                lcstab[i][j].prev = NULL;
            }
            else if (str1[i - 1] == str2[j - 1]) {
                lcstab[i][j].score = lcstab[i - 1][j - 1].score + 1;
                lcstab[i][j].letter = str1[i - 1];
                lcstab[i][j].prev = &lcstab[i - 1][j - 1];
                if (lcstab[i][j].score > max) {
                    max = lcstab[i][j].score;
                    head = &lcstab[i][j];
                }
            }
            else {
                lcstab[i][j].score = 0;
                lcstab[i][j].letter = 0;
                lcstab[i][j].prev = NULL;
            }
        }
    }

    /* Allocate the output array and copy the LC substring */
    *result = malloc(max + 1);
    (*result)[max] = '\0';
    for (i = max - 1; head->prev != NULL; i--) {
        (*result)[i] = head->letter;
        head = head->prev;
    } 
    for (i = 0; i < m + 1; i++) {
        free(lcstab[i]);
    }
    free(lcstab);
    return max;
}

An example program:

int main(void)
{
    char str1[] = "magnetohydrodynamics";
    char str2[] = "hydrogen";
    char *result;
 
    printf("Length of Longest Common Substring is %u\n", 
            longest_common_substring(str1, str2, &result));
    printf("%s\n", result);
    free(result);

    return 0;
}

The output:

Length of Longest Common Substring is 5
hydro

Longest Increasing Subsequence using dynamic programming in C

A longest increasing subsequence (LIS) of a sequence is a maximal subsequence which is not necessarily contiguous, and is monotonically increasing across its length, and is as long as the longest such subsequence for that sequence. A given sequence may have more than one longest increasing subsequence.

This is a dynamic programming algorithm for finding an LIS of a sequence of integers. It works by building chains of increasing subsequences as it scans the main sequence, and keeping track of a maximum one. At the end of the scan the maximum subsequence chain is read back and copied to an output array.

struct lis_entry {
    int value;
    int score;
    struct lis_entry *prev;
};
typedef struct lis_entry lis_entry;

unsigned int longest_increasing_subsequence(const unsigned int *arr, size_t len,
        unsigned int **result)
{
    lis_entry *lis;
    unsigned int i, j, max = 0;
    lis_entry *head;

    lis = malloc(len * sizeof(lis_entry));
    if (lis == NULL) {
        return 0;
    }

    /* Initialise entries */
    for (i = 0; i < len; i++ ) {
        lis[i].value = arr[i];
        lis[i].score = 1;
        lis[i].prev = NULL;
    }
 
    /* Calculate LIS scores and build chains */
    for (i = 1; i < len; i++ ) {
        for (j = 0; j < i; j++ ) {
            if (arr[i] > arr[j] && lis[i].score < lis[j].score + 1) {
                lis[i].score = lis[j].score + 1;
                lis[i].prev = &lis[j];
                if (lis[i].score > max) {
                    max = lis[i].score;
                    head = &lis[i];
                }
            }
        }
    }

    /* Allocate the output array and copy the max chain */
    *result = malloc(max * sizeof(int));
    if (*result != NULL) {
        for (i = max - 1; head != NULL; i--) {
            (*(result))[i] = head->value;
            head = head->prev;
        }
    }
    else {
        max = 0;
    }
 
    free(lis);
 
    return max;
}

An example program using the first few terms of the Van der Corput Sequence:

int main(void)
{
    unsigned int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
    const size_t len = sizeof(arr)/sizeof(arr[0]);
    unsigned int *result;
    unsigned int i;
    unsigned int lis_length = longest_increasing_subsequence(arr, len, &result);
    printf("Length of LIS is %d\n", lis_length);
    for (i = 0; i < lis_length; i++) {
        printf("%u\n", result[i]);
    }
    free(result);
    return 0;
}

Output:

Length of LIS is 6
0
4
6
9
13
15

Longest Common Subsequence in C

This Longest Common Subsequence (LCS) algorithm is a classic dynamic programming table-filling algorithm.

static size_t longest_common_subsequence_internal(const char *str1, const char *str2, matrix **mat)
{
    int i, j;
    const size_t alen = strlen(str1);
    const size_t blen = strlen(str2);
    *mat = matrix_create(alen, blen);
    if (*mat == NULL) {
        return 0;
    }
    for (i = alen - 1; i >= 0; i--) {
	    for (j = blen - 1; j >= 0; j--) {
            if (str1[i] == str2[j]) {
                matrix_set(*mat, i, j, 1 + matrix_get(*mat, i + 1, j + 1));
            }
            else {
                matrix_set(*mat, i, j, max(matrix_get(*mat, i + 1, j), matrix_get(*mat, i, j + 1)));
            }
	    }
    }
    return matrix_get(*mat, 0, 0);
}

size_t longest_common_subsequence_length(const char *str1, const char *str2)
{
    matrix *mat;
    size_t result = longest_common_subsequence_internal(str1, str2, &mat);
    matrix_delete(mat);
	return result;
}

char *longest_common_subsequence(const char *str1, const char *str2)
{
    matrix *mat;
    size_t lcs_len = longest_common_subsequence_internal(str1, str2, &mat);
    unsigned int i = 0;
    unsigned int j = 0;
    unsigned int k = 0;
    const unsigned int alen = strlen(str1);
    const unsigned int blen = strlen(str2);
    char *lcs = malloc(lcs_len + 1);
    while (i < alen && j < blen) {
        if (str1[i] == str2[j]) {
            lcs[k] = str1[i];
            i++;
            j++;
            k++;
        }
        else if (matrix_get(mat, i + 1, j) >= matrix_get(mat, i ,j + 1)) {
            i++;
        }
        else {
            j++;
        }
    }
    lcs[k] = '\0';
    matrix_delete(mat);
    return lcs;
}

Example program:

int main(void)
{
    char str1[] = "pAqBrCs";
    char str2[] = "wAxByCz";
    char *lcs;
    lcs = longest_common_subsequence(str1, str2);
    printf("The longest common subsequence is \"%s\"\n", lcs);
    free(lcs);
    return 0;
}
The longest common subsequence is "ABC"

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.