Tag Archives: Fractional Knapsack

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)