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.

Graph in C

This is a an implementation of a graph data structure, using what might be called the "intuitive" or "object-orented" representation, in which the graph is stored in memory as a set of vertices and a set of edges. It uses a sorted array as the set data structure.

Here is the header file (graph1.h):

#ifndef GRAPH1_H
#define GRAPH1_H

#include <sortedarray.h>
#include <vertex.h>
#include <edge.h>
#include <iterator.h>

typedef struct {
	sortedarray * vertices;
	sortedarray * edges;
} graph1;

graph1 *graph1_create(void);
void graph1_delete(graph1 *graph);
vertex * graph1_add(graph1 *graph, const char *name, void *data);
vertex * graph1_get_vertex(const graph1 *graph, const char *name);
void * graph1_remove(graph1 *graph, vertex *v);
void graph1_add_edge(graph1 *graph, vertex *vertex1, vertex *vertex2);
void graph1_remove_edge(graph1 *graph, vertex *vertex1, vertex *vertex2);
unsigned int graph1_get_adjacent(const graph1 *graph, const vertex *vertex1, const vertex *vertex2);
iterator *graph1_get_neighbours(const graph1 *graph, const vertex *v);
iterator *graph1_get_edges(const graph1 *graph);
iterator *graph1_get_vertices(const graph1 *graph);
unsigned int graph1_get_neighbour_count(const graph1 * graph, const vertex * v);
unsigned int graph1_get_edge_count(const graph1 * graph);
unsigned int graph1_get_vertex_count(const graph1 * graph);

#endif /* GRAPH1_H */

And here is an example program:

#include <stdio.h>

#include <graph1.h>

int main(void)
{
    graph1 *graph;
    vertex *v;
    vertex *A, *B, *C, *D, *E;
    iterator *vertices, *edges;
    edge *e;

    /* Create a graph */
    graph = graph1_create();

    /* Add vertices */
    A = graph1_add(graph, "A", NULL);
    B = graph1_add(graph, "B", NULL);
    C = graph1_add(graph, "C", NULL);
    D = graph1_add(graph, "D", NULL);
    E = graph1_add(graph, "E", NULL);

    /* Add edges */
    graph1_add_edge(graph, A, B);
    graph1_add_edge(graph, A, D);
    graph1_add_edge(graph, B, C);
    graph1_add_edge(graph, C, B);
    graph1_add_edge(graph, D, A);
    graph1_add_edge(graph, D, C);
    graph1_add_edge(graph, D, E);

    /* Display */
    printf("Vertices (%d) and their neighbours:\n\n", graph1_get_vertex_count(graph));
    vertices = graph1_get_vertices(graph);
    while ((v = iterator_get(vertices))) {
        iterator *neighbours;
        vertex *neighbour;
        unsigned int n = 0;
        printf("%s (%d): ", vertex_get_name(v), graph1_get_neighbour_count(graph, v));
        neighbours = graph1_get_neighbours(graph, v);
        while ((neighbour = iterator_get(neighbours))) {
            printf("%s", vertex_get_name(neighbour));
            if (n < graph1_get_neighbour_count(graph, v) - 1) {
                fputs(", ", stdout);
            }
            n++;
        }
        putchar('\n');
        iterator_delete(neighbours);
    }
    putchar('\n');
    iterator_delete(vertices);
    printf("Edges (%d):\n\n", graph1_get_edge_count(graph));
    edges = graph1_get_edges(graph);
    while ((e = iterator_get(edges))) {
        printf("%s -> %s\n", vertex_get_name(edge_get_from(e)), vertex_get_name(edge_get_to(e)));
    }
    putchar('\n');
    iterator_delete(edges);

    /* Delete */
    graph1_delete(graph);

    return 0;
}

This is the output:

Vertices (5) and their neighbours:

A (2): B, D
B (1): C
C (1): B
D (3): A, C, E
E (0):

Edges (7):

A -> B
A -> D
B -> C
C -> B
D -> A
D -> C
D -> E

This is the implementation (graph1.c):

#include <stdlib.h>

#include <edge.h>
#include <sortedarray-iterator.h>

#include <graph1.h>

graph1 *graph1_create(void)
{
	graph1 *graph = malloc(sizeof(graph1));
	if (graph) {
		graph->vertices = sortedarray_create((sortedarray_cmpfn)vertex_compare);
		graph->edges = sortedarray_create((sortedarray_cmpfn)edge_compare);
	}
	return graph;
}

void graph1_delete(graph1 *graph)
{
	if (graph) {
		sortedarray_for_each(graph->vertices, (sortedarray_forfn)vertex_delete);
		sortedarray_delete(graph->vertices);
		sortedarray_for_each(graph->edges, (sortedarray_forfn)edge_delete);
		sortedarray_delete(graph->edges);
		free(graph);
	}
}

vertex *graph1_add(graph1 *graph, const char *name, void *data)
{
	vertex *v = vertex_create(name, data, NULL, NULL);
	vertex *existing = sortedarray_add(graph->vertices, v);
	vertex_delete(existing);
	return v;
}

vertex *graph1_get_vertex(const graph1 *graph, const char *name)
{
	vertex *v = sortedarray_find(graph->vertices, &name);
	return v;
}

void *graph1_remove(graph1 *graph, vertex *v)
{
	vertex * removed;
	void *data;
	unsigned int e = 0;

	/* Remove the edges belonging to this vertex */
	while (e < sortedarray_get_count(graph->edges)) {
		edge *edge = sortedarray_get(graph->edges, e);
		if (edge->from == v || edge->to == v) {
			sortedarray_remove_at(graph->edges, e);
			edge_delete(edge);
		}
		else {
			e++;
		}
	}
	/* Remove the vertex */
	removed = sortedarray_remove(graph->vertices, v);
	if (removed) {
		data = removed->data;
		vertex_delete(removed);
	}

	return data;
}

void graph1_add_edge(graph1 *graph, vertex *vertex1, vertex *vertex2)
{
	edge *e = edge_create(vertex1, vertex2);
	edge *existing = sortedarray_add(graph->edges, e);
	edge_delete(existing);
}

void graph1_remove_edge(graph1 *graph, vertex *vertex1, vertex *vertex2)
{
	unsigned int i;
	unsigned int removed = 0;

	for (i = 0; i < sortedarray_get_count(graph->edges) && !removed; i++) {
		edge *e = sortedarray_get(graph->edges, i);
		if (e->from == vertex1 && e->to == vertex2) {
			sortedarray_remove_at(graph->edges, i);
			edge_delete(e);
			removed = 1;
		}
	}
}

unsigned int graph1_get_adjacent(const graph1 *graph, const vertex *vertex1, const vertex *vertex2)
{
	unsigned int adjacent = 0;
	unsigned int i;

	for (i = 0; i < sortedarray_get_count(graph->edges) && !adjacent; i++) {
		const edge *e = sortedarray_get(graph->edges, i);
		adjacent = e->from == vertex1 && e->to == vertex2;
	}

	return adjacent;
}

unsigned int graph1_get_neighbour_count(const graph1 * graph, const vertex * vertex)
{
	/* The neighbour count is the count of edges that are from this vertex */
	unsigned int i;
	unsigned int edges = 0;

	for (i = 0; i < sortedarray_get_count(graph->edges); i++) {
		const edge *e = sortedarray_get(graph->edges, i);
		edges += e->from == vertex;
	}

	return edges;
}

unsigned int graph1_get_edge_count(const graph1 * graph)
{
	return sortedarray_get_count(graph->edges);
}

unsigned int graph1_get_vertex_count(const graph1 * graph)
{
	return sortedarray_get_count(graph->vertices);
}

typedef struct {
	const graph1 *graph;
	const vertex *v;
	unsigned int current;
} neighbour_iterator;

static neighbour_iterator *neighbour_iterator_create(const graph1 *graph, const vertex *v)
{
	neighbour_iterator *it = malloc(sizeof(neighbour_iterator));
	if (it) {
		it->graph = graph;
		it->v = v;
		it->current = 0;
	}
	return it;
}

static void neighbour_iterator_delete(neighbour_iterator *it)
{
	free(it);
}

static void *neighbour_iterator_get(neighbour_iterator *it)
{
	vertex *neighbour = NULL;
	for (;it->current < sortedarray_get_count(it->graph->edges) && neighbour == NULL; it->current++) {
		const edge *e = sortedarray_get(it->graph->edges, it->current);
		if (e->from == it->v) {
			neighbour = e->to;
		}	
	}
	return neighbour;
}

iterator *graph1_get_neighbours(const graph1 *graph, const vertex *v)
{
	return iterator_create(neighbour_iterator_create(graph, v), 
		(iterator_getfn)neighbour_iterator_get, (iterator_deletefn)neighbour_iterator_delete);
}

iterator *graph1_get_edges(const graph1 *graph)
{
	return sortedarray_get_iterator(graph->edges);
}

iterator *graph1_get_vertices(const graph1 *graph)
{
	return sortedarray_get_iterator(graph->vertices);
}

This is the header file for a polymorphic vertex type that can be used by several different graph representations (vertex.h):

#ifndef VERTEX_H
#define VERTEX_H

typedef void (*vertex_deletefn)(void *);

typedef struct {
	char * name;
	void * data;
	void * body;
	vertex_deletefn del;
} vertex;

vertex *vertex_create(const char *name, void *data, void *body, vertex_deletefn del);
void vertex_delete(vertex *v);
int vertex_compare(const vertex *vertex1, const vertex *vertex2);
const char *vertex_get_name(const vertex *v);
void *vertex_get_data(const vertex *v);

#endif /* VERTEX_H */

And this is its implementation (vertex.c):

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

#include <vertex.h>

vertex * vertex_create(const char *name, void *data, void *body, vertex_deletefn del)
{
	vertex *v = malloc(sizeof(vertex));
	if (v) {
		v->name = strdup(name);
		v->data = data;
		v->body = body;
		v->del = del;
	}
	return v;
}

void vertex_delete(vertex *v)
{
	if (v) {
		free(v->name);
		if (v->del) {
			v->del(v->body);
		}
		free(v);
	}
}

int vertex_compare(const vertex *vertex1, const vertex *vertex2)
{
	return strcmp(vertex1->name, vertex2->name);
}

const char * vertex_get_name(const vertex *v)
{
	return v->name;
}

void * vertex_get_data(const vertex *v)
{
	return v->data;
}

This is the header file for the edge type (edge.h):

#ifndef EDGE_H
#define EDGE_H

#include <vertex.h>

typedef struct {
	vertex *from;
	vertex *to;
} edge;

edge *edge_create(vertex* from, vertex *to);
void edge_delete(edge *e);
int edge_compare(const edge *edge1, const edge *edge2);
const vertex *edge_get_from(const edge * e);
const vertex *edge_get_to(const edge * e);

#endif /* EDGE_H */

And this is the implementation (edge.c):

#include <stdlib.h>

#include <edge.h>

edge *edge_create(vertex* from, vertex *to)
{
	edge *e = malloc(sizeof(edge));
	if (e) {
		e->from = from;
		e->to = to;
	}

	return e;
}

void edge_delete(edge *e) 
{
	free(e);
}

int edge_compare(const edge *edge1, const edge *edge2)
{
	int result = vertex_compare(edge1->from, edge2->from);
	if (result == 0) {
		result = vertex_compare(edge1->to, edge2->to);
	}
	return result;
}

const vertex * edge_get_from(const edge * e)
{
	return e->from;
}

const vertex * edge_get_to(const edge * e)
{
	return e->to;
}

This is the header file for polymorphic iterators (iterator.h):

#ifndef ITERATOR_H
#define ITERATOR_H

typedef void (*iterator_deletefn)(void *);
typedef void *(*iterator_getfn)(void *);

struct iterator {
	void *      body;
	iterator_getfn     get;
	iterator_deletefn  del;
};
typedef struct iterator iterator;

iterator *iterator_create(void *body, iterator_getfn get, iterator_deletefn del);
void iterator_delete(iterator *it);
void *iterator_get(iterator *it);

#endif /* ITERATOR_H */

And this is the implementation (iterator.c):

#include <stdlib.h>

#include <iterator.h>

iterator *iterator_create(void *body, iterator_getfn get, iterator_deletefn del)
{
	iterator *it = malloc(sizeof(iterator));
	if (it) {
		it->body = body;
		it->get = get;
		it->del = del;
	}

	return it;
}

void iterator_delete(iterator *it)
{
	if (it) {
		if (it->del) {
			it->del(it->body);
		}
		free(it);
	}
}

void *iterator_get(iterator *it)
{
	return it->get(it->body);
}

This is the header file for the sorted array iterator (sortedarray-iterator.h):

#ifndef SORTEDARRAY_ITERATOR_H
#define SORTEDARRAY_ITERATOR_H

#include <iterator.h>
#include <sortedarray.h>

iterator *sortedarray_get_iterator(const sortedarray * array);

#endif /* SORTEDARRAY_ITERATOR_H */

And the implementation (sortedarray-iterator.c):

#include <dynarray-iterator.h>

#include <sortedarray-iterator.h>

iterator * sortedarray_get_iterator(const sortedarray * array)
{
	return dynarray_get_iterator(array->array);
}

This is the header file for the dynamic array iterator (dynarray-iterator.h):

#ifndef DYNARRAY_ITERATOR_H
#define DYNARRAY_ITERATOR_H

#include <iterator.h>
#include <dynarray.h>

iterator *dynarray_get_iterator(const dynarray *array);

#endif /* DYNARRAY_ITERATOR_H */

And this is the implementation (dynarray-iterator.c):

#include <stdlib.h>

#include <dynarray-iterator.h>

typedef struct {
	const dynarray *array;
	unsigned int current;
} dynarray_iterator;

static dynarray_iterator *dynarray_iterator_create(const dynarray *array)
{
	dynarray_iterator *it = malloc(sizeof(dynarray_iterator));
	if (it) {
		it->array = array;
		it->current = 0;
	}
	return it;
}

static void dynarray_iterator_delete(dynarray_iterator *it)
{
	free(it);
}

static void *dynarray_iterator_get(dynarray_iterator *it)
{
	void *data = NULL;
	if (it->current < it->array->count) {
		data = dynarray_get(it->array, it->current);
		it->current++;
	}
	return data;
}

iterator *dynarray_get_iterator(const dynarray *array)
{
	return iterator_create(dynarray_iterator_create(array), (iterator_getfn)dynarray_iterator_get, 
		(iterator_deletefn)dynarray_iterator_delete);
}

Of internal and external iterators, and generators

Internal iterators

  • Are easy to write because you can use loops and recursion
  • Can’t be controlled by the client (except for stopping early)
  • Don’t suffer from invalidation because only one can be in operation at once (unless the container is being accessed by multiple threads)
  • Don’t need to hold on to precious resources like files and network and database connections for an unpredictable length of time
  • Can’t run in parallel, or be interleaved
  • Can only be nested by passing callbacks to callbacks

External iterators

  • Are more difficult to write because you need to maintain state and can’t use loops and recursion
  • Are controlled by the client
  • Can be run in parallel or interleaved
  • May be invalidated – you need to specify invalidation behaviour or make them robust
  • May need to hold on to precious resources like files and network and database connections for an unpredictable length of time
  • – although you can implement timeouts and lazy connects

Generators

Generators give you the best of both worlds, in the sense that they are as easy to write as internal iterators, but are exposed as external iterators.
Because they are external iterators, they can be invalidated, and can hold on to resources for an unpredictable length of time.

Downloading a Web page in Java using a java.net.Socket

import java.io.*;
import java.net.*;
 
public class SocketHTTPClient {
    public static void main(String[] args) {
         
        String hostName = "www.martinbroadhurst.com";
        int portNumber = 80;
 
        try {
            Socket socket = new Socket(hostName, portNumber);
            PrintWriter out =
                new PrintWriter(socket.getOutputStream(), true);
            BufferedReader in =
                new BufferedReader(
                    new InputStreamReader(socket.getInputStream()));
            out.println("GET / HTTP/1.1\nHost: www.martinbroadhurst.com\n\n");
            String inputLine;
            while ((inputLine = in.readLine()) != null) {
                System.out.println(inputLine);
            }
        } catch (UnknownHostException e) {
            System.err.println("Don't know about host " + hostName);
            System.exit(1);
        } catch (IOException e) {
            System.err.println("Couldn't get I/O for the connection to " +
                hostName);
            System.exit(1);
        } 
    }
}