# 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];
}
}

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