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, ¤t_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