Fractional Knapsack

A thief has a bag of capacity c: the total weight cannot exceed c. A shop contains n kinds of items. Item i has weight $w_i$ and value $v_i$ . How should items be selected to maximize total value?

Suppose the capacity is 30 and the items have the following weights and values:

Item	1	2	3	4	5
Weight w	10	5	15	10	20
Value v	20	30	15	25	10

Fractional knapsack has optimal substructure: after selecting part of the items, the remaining capacity and remaining items form a subproblem that must also be solved optimally. To maximize the final value, give priority to items with the greatest value per unit of weight. Once one is used up, continue with the next highest value density.

Fractional knapsack

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double weight;
    double value;
    double unit_value;
} Item;

Item item_create(double weight, double value) {
    Item item;
    item.weight = weight;
    item.value = value;
    item.unit_value = value / weight;
    return item;
}

static int cmp(const void *obj1, const void *obj2) {
    Item *item1 = (Item *)obj1;
    Item *item2 = (Item *)obj2;
    if (item1->unit_value > item2->unit_value) {
        return -1;
    } else if (item1->unit_value < item2->unit_value) {
        return 1;
    } else {
        return 0;
    }
}

int knapsack(Item *items, int item_num, int capacity, Item *selected_items) {
    qsort(items, item_num, sizeof(Item), cmp);

    int selected_num = 0;
    double selected_weight = 0;

    for (int i = 0; i < item_num; i++) {
        if (selected_weight >= capacity) {
            break;
        }
        if (selected_weight + items[i].weight <= capacity) {
            selected_weight += items[i].weight;
            selected_items[selected_num] = items[i];
            selected_num++;
        } else {
            double portion = (capacity - selected_weight) / items[i].weight;
            items[i].weight *= portion;
            items[i].value *= portion;
            selected_items[selected_num] = items[i];
            selected_num++;
            break;
        }
    }

    return selected_num;
}

int main(void) {
    Item items[] = {
        item_create(10, 20),
        item_create(5, 30),
        item_create(15, 15),
        item_create(10, 25),
        item_create(20, 10),
    };
    int item_num = sizeof(items) / sizeof(items[0]);
    int capacity = 30;

    Item selected_items[item_num];
    int selected_num = knapsack(items, item_num, capacity, selected_items);
    for (int i = 0; i < selected_num; i++) {
        printf("Item(weight=%.2f, value=%.2f, unit_value=%.2f)\n",
               selected_items[i].weight,
               selected_items[i].value,
               selected_items[i].unit_value);
    }

    return 0;
}

QUESTION

Why can fractional knapsack select by value density?

QUESTION

An item weighs 10 and is worth 25. With room for 4, what value does its fraction add?

Item 1

w=4, v=20

v/w=5

Item 2

w=8, v=24

v/w=3

Item 3

w=10, v=20

v/w=2

Capacity: 0 / 16

Capacity 16; items are divisible. Calculate densities, packing order, each selected fraction and total value. Explain how the last item’s weight and value scale together.

Fractional Knapsack

A thief has a bag of capacity c: the total weight cannot exceed c. A shop contains n kinds of items. Item i has weight

w_i

and value

v_i

. How should items be selected to maximize total value?

Suppose the capacity is 30 and the items have the following weights and values:

Item

Weight w

Value v

Fractional knapsack

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    double weight;
    double value;
    double unit_value;
} Item;

Item item_create(double weight, double value) {
    Item item;
    item.weight = weight;
    item.value = value;
    item.unit_value = value / weight;
    return item;
}

static int cmp(const void *obj1, const void *obj2) {
    Item *item1 = (Item *)obj1;
    Item *item2 = (Item *)obj2;
    if (item1->unit_value > item2->unit_value) {
        return -1;
    } else if (item1->unit_value < item2->unit_value) {
        return 1;
    } else {
        return 0;
    }
}

int knapsack(Item *items, int item_num, int capacity, Item *selected_items) {
    qsort(items, item_num, sizeof(Item), cmp);

    int selected_num = 0;
    double selected_weight = 0;

    for (int i = 0; i < item_num; i++) {
        if (selected_weight >= capacity) {
            break;
        }
        if (selected_weight + items[i].weight <= capacity) {
            selected_weight += items[i].weight;
            selected_items[selected_num] = items[i];
            selected_num++;
        } else {
            double portion = (capacity - selected_weight) / items[i].weight;
            items[i].weight *= portion;
            items[i].value *= portion;
            selected_items[selected_num] = items[i];
            selected_num++;
            break;
        }
    }

    return selected_num;
}

int main(void) {
    Item items[] = {
        item_create(10, 20),
        item_create(5, 30),
        item_create(15, 15),
        item_create(10, 25),
        item_create(20, 10),
    };
    int item_num = sizeof(items) / sizeof(items[0]);
    int capacity = 30;

    Item selected_items[item_num];
    int selected_num = knapsack(items, item_num, capacity, selected_items);
    for (int i = 0; i < selected_num; i++) {
        printf("Item(weight=%.2f, value=%.2f, unit_value=%.2f)\n",
               selected_items[i].weight,
               selected_items[i].value,
               selected_items[i].unit_value);
    }

    return 0;
}

QUESTION

Why can fractional knapsack select by value density?

QUESTION

An item weighs 10 and is worth 25. With room for 4, what value does its fraction add?

Item 1

w=4, v=20

v/w=5

Item 2

w=8, v=24

v/w=3

Item 3

w=10, v=20

v/w=2

Capacity: 0 / 16

Capacity 16; items are divisible. Calculate densities, packing order, each selected fraction and total value. Explain how the last item’s weight and value scale together.

Fractional Knapsack