Knapsack Problem in C and C++: 0/1 Dynamic Programming, Item Recovery and the Fractional Variant

Four items, a bag that holds 50 units of weight, and a question: which items give the most value? The obvious strategy, packing the best value-per-weight items first, returns 210 on the example below. The best answer is 230. Getting there needs dynamic programming, and getting the items rather than just the number needs one more step that the bare recurrence does not give you.

This article covers the 0/1 knapsack recurrence, a C implementation that reports which items were chosen, the one-row version and why its loop must run downwards, the fractional variant, and a C++ version. Every program was compiled and run for this article on Ubuntu 24.04 with GCC 13.3 and Clang 18.1.3 under -std=c11 and -std=c17 (C++: -std=c++17 and -std=c++20) with -Wall -Wextra -pedantic and no warnings, and every output block is captured verbatim. The code is in two GitHub repositories whose builds run the same tests on each commit, including a pass under AddressSanitizer and UndefinedBehaviorSanitizer.

What Is the Knapsack Problem?

The knapsack problem asks which subset of items to pack so that their total value is as large as possible while their total weight stays within a fixed capacity. In the 0/1 version each item is either taken whole or left out. Dynamic programming solves it in O(n × W) time, where n is the number of items and W the capacity.

The problem has been studied since at least 1897, according to the history summarised on the Wikipedia knapsack problem page. Its decision form (“can a total value of at least V fit?”) is NP-complete, which is why the O(n × W) algorithm is described as pseudo-polynomial: the running time grows with the numeric size of W, not with the number of digits needed to write it. The section on complexity below measures what that means in practice.

Four variants come up often enough to name:

Every example in this article uses the same four items and a capacity of 50:

Why Greedy Fails for 0/1 Knapsack

The greedy idea is to sort by value per unit weight and take each item that still fits. On these items it takes D, then A, then B, reaching weight 35 and value 210. C weighs 30 and no longer fits, so 15 units of capacity go unused.

static long long greedy_by_ratio(const Item *it, size_t n, int cap)
{
    long long total = 0;
    for (size_t i = 0; i < n; i++)
        if (it[i].weight <= cap) {
            cap -= it[i].weight;
            total += it[i].value;
        }
    return total;
}

Run on the items in ratio order, alongside the correct dynamic programming answer (lines 1 and 3 of the pitfall program’s output):

0/1 DP, capacities downward : 230
Greedy by value/weight      : 210

The optimal set is A, C and D: weight 45, value 230. It skips B even though B has a better ratio than C, because B and C cannot both fit alongside A and D, and C contributes more value. A greedy choice made early cannot be undone later, and in 0/1 knapsack the early choice is sometimes wrong.

Greedy is not always the wrong tool. Kruskal’s algorithm for minimum spanning trees is greedy and provably optimal, and greedy is also optimal for the fractional knapsack later in this article. What breaks it here is that items are indivisible.

The Dynamic Programming Recurrence

Define best[i][c] as the highest value achievable using only the first i items with capacity c. For each item there are two choices:

1. Leave item i out. The value is whatever the first i − 1 items achieved at the same capacity: best[i − 1][c].
2. Take item i, if its weight w is at most c. Its value v is added to the best the first i − 1 items can do in the remaining capacity: v + best[i − 1][c − w].

best[0][c] = 0
best[i][c] = best[i-1][c]                                   if w[i] > c
best[i][c] = max(best[i-1][c], v[i] + best[i-1][c - w[i]])  otherwise

The answer is best[n][W]. Each cell depends only on the row above it, which is what makes both the one-row optimisation and the item recovery below possible. The same “solve each subproblem once and reuse it” idea appears in memoised Fibonacci, covered in Fibonacci series in C and C++ with memoization; knapsack adds a second dimension.

The cell above the answer is worth a look. With only A, B and C available, the best at capacity 50 is 220 (B and C). Adding D raises it to 230 by changing the whole selection, not by adding D to B and C, which would weigh 55.

0/1 Knapsack in C

The listing below is a complete program with two functions. knapsack_value returns only the best value and uses a single row of capacity + 1 entries. knapsack_select also reports which items were chosen. Both allocate on the heap and validate their input.

#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    const char *name;
    int weight;
    long long value;
} Item;

/* Rejects negative weights or values, and inputs whose total value
   would not fit in a long long (so no sum below can overflow). */
static bool items_valid(const Item *items, size_t n)
{
    long long total = 0;
    for (size_t i = 0; i < n; i++) {
        if (items[i].weight < 0 || items[i].value < 0)
            return false;
        if (items[i].value > LLONG_MAX - total)
            return false;
        total += items[i].value;
    }
    return true;
}

/* Best total value for 0/1 knapsack using one row of size capacity + 1.
   Returns 0 on success, -1 for invalid input, -2 if memory runs out. */
int knapsack_value(const Item *items, size_t n, int capacity, long long *best)
{
    if (capacity < 0 || (n > 0 && items == NULL) || best == NULL)
        return -1;
    if (!items_valid(items, n))
        return -1;

    long long *dp = calloc((size_t)capacity + 1, sizeof *dp);
    if (dp == NULL)
        return -2;

    for (size_t i = 0; i < n; i++) {
        int wt = items[i].weight;
        long long val = items[i].value;
        /* Downwards, so dp[c - wt] still holds the value without item i. */
        for (int c = capacity; c >= wt; c--) {
            if (dp[c - wt] + val > dp[c])
                dp[c] = dp[c - wt] + val;
        }
    }

    *best = dp[capacity];
    free(dp);
    return 0;
}

/* Same answer, plus which items achieve it. take[i] is set to true for
   every chosen item. Uses one byte per (item, capacity) cell. */
int knapsack_select(const Item *items, size_t n, int capacity,
                    long long *best, bool *take)
{
    if (capacity < 0 || (n > 0 && (items == NULL || take == NULL)) || best == NULL)
        return -1;
    if (!items_valid(items, n))
        return -1;

    size_t cols = (size_t)capacity + 1;
    if (n > 0 && cols > SIZE_MAX / n)
        return -2;

    long long *dp = calloc(cols, sizeof *dp);
    unsigned char *kept = calloc(n * cols, 1);
    if (dp == NULL || (n > 0 && kept == NULL)) {
        free(dp);
        free(kept);
        return -2;
    }

    for (size_t i = 0; i < n; i++) {
        int wt = items[i].weight;
        long long val = items[i].value;
        for (int c = capacity; c >= wt; c--) {
            if (dp[c - wt] + val > dp[c]) {
                dp[c] = dp[c - wt] + val;
                kept[i * cols + (size_t)c] = 1;
            }
        }
    }

    /* Walk back from the last item: if item i improved capacity c, it is in. */
    int c = capacity;
    for (size_t i = n; i-- > 0;) {
        take[i] = kept[i * cols + (size_t)c];
        if (take[i])
            c -= items[i].weight;
    }

    *best = dp[capacity];
    free(dp);
    free(kept);
    return 0;
}

int main(void)
{
    const Item items[] = {
        {"A", 10, 60}, {"B", 20, 100}, {"C", 30, 120}, {"D", 5, 50},
    };
    const size_t n = sizeof items / sizeof items[0];
    const int capacity = 50;

    long long best;
    bool take[sizeof items / sizeof items[0]];

    if (knapsack_select(items, n, capacity, &best, take) != 0) {
        fputs("knapsack_select failed\n", stderr);
        return EXIT_FAILURE;
    }

    int used = 0;
    printf("Capacity %d, best value %lld\n", capacity, best);
    for (size_t i = 0; i < n; i++) {
        if (take[i]) {
            printf("  take %s  weight %2d  value %3lld\n",
                   items[i].name, items[i].weight, items[i].value);
            used += items[i].weight;
        }
    }
    printf("Weight used: %d of %d\n", used, capacity);

    long long check;
    if (knapsack_value(items, n, capacity, &check) != 0 || check != best) {
        fputs("knapsack_value disagrees\n", stderr);
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

Output:

Capacity 50, best value 230
  take A  weight 10  value  60
  take C  weight 30  value 120
  take D  weight  5  value  50
Weight used: 45 of 50

A few decisions in this code are deliberate, and each one closes off a failure that compiles cleanly:

• Values are long long and the total is checked up front. items_valid rejects any input whose values sum past LLONG_MAX. Because no partial sum can exceed the total, no addition inside the loops can overflow, which is signed-integer undefined behaviour in C.
• Negative weights and values are rejected. A negative weight would make c - wt larger than c and index past the end of dp.
• The size calculation is checked before allocating. n * cols is computed in size_t, and the function returns -2 rather than letting the product wrap around to a small number.
• Zero-weight items work. With wt == 0 the inner loop runs from capacity down to 0, adding the item’s value once at each capacity. The tests include this case.

Recovering Which Items Were Chosen

The one-row version overwrites the row on every item, so by the end there is no record of how each value was reached. knapsack_select keeps that record in kept: one byte per (item, capacity) cell, set to 1 when taking item i improved the value at capacity c.

Recovery walks backwards from the last item. If kept[i][c] is set, item i is in the answer and the remaining capacity drops by its weight; otherwise capacity stays the same and the walk moves to the previous item. The figure above traces exactly this path: D is taken (capacity 50 → 45), C is taken (45 → 15), B is skipped, A is taken (15 → 5).

Storing kept as bytes instead of keeping the full table of long long values cuts the reconstruction memory by a factor of eight. Packing it as bits would cut it by eight again, at the cost of shifting and masking on every access.

Why the Capacity Loop Runs Downwards

The one-row version works because, when the inner loop reaches capacity c, the entry dp[c - wt] still holds the value from before item i was considered. That is only true if smaller capacities have not been updated yet, so the loop must go from capacity down to wt.

Reverse the direction and dp[c - wt] may already include item i, so the same item can be counted again:

static long long dp_upward(const Item *it, size_t n, int cap, long long *dp)
{
    for (int c = 0; c <= cap; c++)
        dp[c] = 0;
    for (size_t i = 0; i < n; i++)
        for (int c = it[i].weight; c <= cap; c++)
            if (dp[c - it[i].weight] + it[i].value > dp[c])
                dp[c] = dp[c - it[i].weight] + it[i].value;
    return dp[cap];
}

Lines 1 and 2 of the pitfall program’s output:

0/1 DP, capacities downward : 230
0/1 DP, capacities upward   : 500

500 is item D taken ten times: ten copies of weight 5 and value 50. The upward loop is not broken code. It is the correct algorithm for the unbounded knapsack, where unlimited copies are allowed. The two problems differ by the direction of one loop, which is why this mistake survives casual testing: it compiles, it runs, and on inputs where repeating an item never helps it returns the right answer.

Where the Table Lives: Stack or Heap

A common way to write the full table in C is a variable-length array:

int dp[n + 1][capacity + 1];

That is valid C99, but C11 made VLAs an optional feature and MSVC does not implement them. The larger problem is where the array lives. A VLA is allocated on the stack, and the stack is small: 8 MiB on the Ubuntu test machine (ulimit -s printed 8192). With 100 items and a capacity of 100,000, the table needs 101 × 100,001 × 4 = 40,400,404 bytes.

The repository’s stack_table.c runs a small case and then that large one. Built with AddressSanitizer:

small: 230
AddressSanitizer:DEADLYSIGNAL
=================================================================
==2750==ERROR: AddressSanitizer: stack-overflow on address 0x7ffc35390058 (pc 0x55e57a3f53f3 bp 0x7ffc35b8b0d0 sp 0x7ffc3538f060 T0)
    #0 0x55e57a3f53f3 in knapsack_vla pitfalls/stack_table.c:10
    #1 0x55e57a3f5eb9 in main pitfalls/stack_table.c:36

Without the sanitizer, the program printed the small result and then died with a segmentation fault (exit status 139). The small case is the trap: the code is correct, passes a textbook example, and fails only once the inputs grow. knapsack_select handles the same 100-item, capacity-100,000 input from the heap and returns 5035, using 10,000,100 bytes for kept and 800,008 for the row.

Allocation with calloc also gives the program a way to fail politely. A failed calloc returns NULL, which the code turns into an error code. A stack overflow gives the program no such chance. (On Linux with memory overcommit enabled, a very large request can appear to succeed and fail later when the pages are touched, so the check is necessary but not a guarantee.)

Time and Space Complexity

O(n × W) looks polynomial, but W is a number in the input, not a count of items. Scaling every weight and the capacity by the same factor leaves the answer unchanged and multiplies the work. The pitfall program does exactly that with the four example items (lines 4 to 7 of its output):

Weights x1    capacity     50  best 230  cells 204
Weights x10   capacity    500  best 230  cells 2004
Weights x100  capacity   5000  best 230  cells 20004
Weights x1000 capacity  50000  best 230  cells 200004

Same four items, same answer, a thousand times the cells. Writing the capacity takes only a few more digits each time, while the table grows in proportion to its value. That is what pseudo-polynomial means, and it is why dividing all weights by their greatest common divisor before running the DP can be a large saving when the data allows it. In this example every weight is a multiple of 5, so the table could shrink by a factor of five.

Fractional Knapsack in C

When items can be split, the greedy approach from earlier becomes optimal. Sort by value per unit weight, take whole items while they fit, then take whatever fraction of the next item fills the remaining capacity. An exchange argument shows why: if an optimal solution left capacity holding a lower-ratio item while a higher-ratio item was not fully used, swapping a little of one for the other would increase the value.

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

typedef struct {
    const char *name;
    int weight;      /* must be > 0 */
    long long value; /* must be >= 0 */
} Item;

/* Higher value per unit of weight first. Compares v1/w1 with v2/w2 as
   v1*w2 against v2*w1, which is exact for weights and values small enough
   that the products fit in a long long. */
static int by_ratio_desc(const void *pa, const void *pb)
{
    const Item *a = pa, *b = pb;
    long long lhs = a->value * b->weight;
    long long rhs = b->value * a->weight;
    return (lhs < rhs) - (lhs > rhs);
}

/* Fractional knapsack: items may be split. Sorts items in place, then
   sets share[i] to the fraction (0.0 to 1.0) of sorted item i that is taken.
   Returns the best value, or -1.0 for invalid input. */
double knapsack_fractional(Item *items, size_t n, int capacity, double *share)
{
    if (capacity < 0 || (n > 0 && (items == NULL || share == NULL)))
        return -1.0;
    for (size_t i = 0; i < n; i++)
        if (items[i].weight <= 0 || items[i].value < 0)
            return -1.0;

    qsort(items, n, sizeof *items, by_ratio_desc);

    double total = 0.0;
    int room = capacity;
    for (size_t i = 0; i < n; i++) {
        if (items[i].weight <= room) {
            share[i] = 1.0;
            room -= items[i].weight;
        } else {
            share[i] = (double)room / items[i].weight;
            room = 0;
        }
        total += share[i] * (double)items[i].value;
    }
    return total;
}

int main(void)
{
    Item items[] = {
        {"A", 10, 60}, {"B", 20, 100}, {"C", 30, 120}, {"D", 5, 50},
    };
    const size_t n = sizeof items / sizeof items[0];

    double share[sizeof items / sizeof items[0]];

    double best = knapsack_fractional(items, n, 50, share);
    if (best < 0.0) {
        fputs("invalid input\n", stderr);
        return EXIT_FAILURE;
    }
    for (size_t i = 0; i < n; i++)
        printf("  %s  value/weight %5.2f  taken %3.0f%%\n", items[i].name,
               (double)items[i].value / items[i].weight, share[i] * 100.0);
    printf("Fractional best value: %.2f\n", best);
    return EXIT_SUCCESS;
}

Output:

  D  value/weight 10.00  taken 100%
  A  value/weight  6.00  taken 100%
  B  value/weight  5.00  taken 100%
  C  value/weight  4.00  taken  50%
Fractional best value: 270.00

The sort uses qsort, so the whole function costs O(n log n); the sorting algorithms comparison covers what qsort guarantees and what it does not. The comparator compares v1 / w1 with v2 / w2 as v1 × w2 against v2 × w1, which avoids floating-point division and its rounding in the sort itself. That holds while the products fit in a long long, as the comment in the code states.

The three answers on the same input line up as they should: greedy whole items 210, optimal 0/1 230, fractional 270. Because the fractional problem relaxes the 0/1 rule, its answer is an upper bound on the 0/1 answer. A branch-and-bound solver can use that bound to discard partial selections that cannot beat the best solution found so far.

0/1 Knapsack in C++

The C++ version uses the same algorithm with standard containers. std::vector owns the memory, so there are no free calls to get wrong, and invalid input is reported with exceptions rather than return codes.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
#include <vector>

struct Item {
    std::string name;
    int weight;
    long long value;
};

struct Selection {
    long long value = 0;
    std::vector<std::size_t> chosen;  // indices into the input, ascending
};

// 0/1 knapsack: best value within capacity, and which items give it.
// Throws std::invalid_argument for negative inputs or a total value that
// would overflow long long; std::bad_alloc if the table does not fit.
Selection knapsack(const std::vector<Item>& items, int capacity)
{
    if (capacity < 0)
        throw std::invalid_argument("capacity must be non-negative");

    long long total = 0;
    for (const Item& it : items) {
        if (it.weight < 0 || it.value < 0)
            throw std::invalid_argument("weights and values must be non-negative");
        if (it.value > std::numeric_limits<long long>::max() - total)
            throw std::invalid_argument("total value overflows long long");
        total += it.value;
    }

    const std::size_t n = items.size();
    const std::size_t cols = static_cast<std::size_t>(capacity) + 1;
    if (n > 0 && cols > std::numeric_limits<std::size_t>::max() / n)
        throw std::bad_alloc();

    std::vector<long long> best(cols, 0);
    std::vector<unsigned char> kept(n * cols, 0);

    for (std::size_t i = 0; i < n; ++i) {
        const int wt = items[i].weight;
        const long long val = items[i].value;
        for (int c = capacity; c >= wt; --c) {  // downwards: each item once
            if (best[c - wt] + val > best[c]) {
                best[c] = best[c - wt] + val;
                kept[i * cols + static_cast<std::size_t>(c)] = 1;
            }
        }
    }

    Selection result;
    result.value = best[static_cast<std::size_t>(capacity)];
    int c = capacity;
    for (std::size_t i = n; i-- > 0;) {
        if (kept[i * cols + static_cast<std::size_t>(c)]) {
            result.chosen.push_back(i);
            c -= items[i].weight;
        }
    }
    std::reverse(result.chosen.begin(), result.chosen.end());
    return result;
}

int main()
{
    const std::vector<Item> items{
        {"A", 10, 60}, {"B", 20, 100}, {"C", 30, 120}, {"D", 5, 50},
    };

    try {
        const Selection s = knapsack(items, 50);
        std::cout << "Best value " << s.value << " from:";
        for (std::size_t i : s.chosen)
            std::cout << ' ' << items[i].name;
        std::cout << '\n';
    } catch (const std::exception& e) {
        std::cerr << "knapsack failed: " << e.what() << '\n';
        return 1;
    }
    return 0;
}

Output:

Best value 230 from: A C D

The differences from the C version are about ownership and error reporting, not the algorithm:

• std::vector<long long> best(cols, 0) replaces calloc; if the allocation fails, std::bad_alloc propagates to the caller.
• Selection returns the chosen indices as a std::vector<std::size_t>, collected backwards and reversed once at the end, rather than inserting at the front each time.
• std::invalid_argument reports negative input or a total that would overflow, so callers cannot ignore an error code by accident.
• std::vector<bool> was not used for kept. It is a bit-packed specialisation that would save memory but returns proxy objects instead of references; std::vector<unsigned char> keeps the C and C++ versions directly comparable.

Testing Against Brute Force

A knapsack implementation can return a plausible number that is wrong, and nothing in the output says so. The test suite checks each implementation against an exhaustive search over every subset, which is too slow for real inputs but has no cleverness to get wrong.

For each of 20,000 random instances (0 to 14 items, capacity 0 to 100, weights 0 to 40 including zero, values 0 to 1000), the tests check that:

• knapsack_value and knapsack_select both match the brute-force best value
• the items knapsack_select reports fit within the capacity
• those items’ values add up to the reported total

Separate tests cover no items, zero capacity, an item heavier than the capacity, an exact fit, zero-weight items, negative weights, a negative capacity, a null output pointer, and values whose total would overflow.

All tests passed (20000 random instances checked against brute force)

A suite that only ever passes proves little about itself, so both suites were also run against a deliberately broken copy with the capacity loop turned upwards. Both failed immediately and stopped after the first ten failures. In C, knapsack_value missed 230 on the worked example and disagreed with brute force on the random instances. In C++, where the broken loop also fed item recovery, the worked example returned the wrong value and the wrong items, and the recovered items stopped adding up to the reported total.

When the Capacity Is Too Large for a Table

The table approach stops being practical once n × W cells no longer fit in memory or time. Other approaches exist, each suited to a different shape of input:

• Dynamic programming over value instead of weight. Index the table by total value and store the minimum weight that achieves it. The cost is O(n × V), where V is the sum of values, which helps when values are small and weights are large.
• Meet in the middle. Split the items into two halves, enumerate the subsets of each, and combine them with sorting and binary search. That costs about O(2^(n/2) × n), which is practical for a few dozen items regardless of the size of the weights.
• Branch and bound. Explore choices item by item and discard any branch whose fractional upper bound cannot beat the best solution found so far.
• Approximation. The knapsack problem has a fully polynomial-time approximation scheme: scaling the values down and running the value-indexed DP gives a solution within a chosen factor of optimal.

For large production instances, try an integer programming solver before writing your own.

Where the Knapsack Problem Shows Up

The structure (pick a subset, a value to maximise, one budget it must fit) appears in many real decisions:

• Budget allocation: choosing projects or features with a fixed amount of money or engineering time
• Loading and packing: filling a container, a truck or a disk with the most valuable items by weight or size
• Test selection: running the subset of tests that covers the most risk within a time limit
• Resource-constrained scheduling: choosing which jobs to run on a machine with fixed memory

Knapsack also has a place in cryptographic history. The Merkle–Hellman cryptosystem, published in 1978, based its security on a knapsack-style problem, and Adi Shamir published a polynomial-time attack on it in 1984, as summarised on the Merkle–Hellman knapsack cryptosystem page. It is a useful lesson in the difference between a problem being hard in general and a particular instance being hard.

Key Takeaways

• Greedy by value per unit weight is not optimal for 0/1 knapsack. On the example it returns 210 against an optimum of 230.
• The recurrence chooses between leaving item i out and taking it, and each cell depends only on the row above, which allows a one-row implementation.
• In the one-row version the capacity loop must run downwards. Running it upwards solves the unbounded problem instead and returned 500 here.
• Recovering the chosen items needs a record of decisions; one byte per cell is enough, and the walk back starts from the bottom-right cell.
• Put the table on the heap. As a stack VLA, the table for 100 items and capacity 100,000 needs 40.4 MB and crashed on an 8 MiB stack.
• O(n × W) is pseudo-polynomial. Scaling the weights by 1,000 left the answer at 230 and multiplied the table size by 1,000.
• Test against brute force on small random inputs. It is what caught the upward-loop mutation in both languages.

Frequently Asked Questions

Conclusion

The knapsack problem rewards care in small places. The recurrence is a few lines, but the direction of one loop decides which problem the code solves, a variable-length array decides whether it survives a realistic input, and a byte per cell decides whether it can say which items it chose.

Brute-force comparison is the habit worth keeping from this one. It is slow, easy to write and hard to get wrong, which makes it the right check on code that is fast and easy to get wrong. The same tables, recurrences and testing approach carry over to the other dynamic programming problems in the top 10 algorithms every programmer should know.

Source Code and Tests

The C code is in mycplus/c-examples and the C++ code in mycplus/cpp-examples. They are separate because the two versions differ exactly where the article is most useful: memory ownership and error reporting.

Build and test either directory with:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

What the badges mean: each workflow builds with warnings treated as errors on GCC and Clang (C11 and C17, or C++17 and C++20) on Ubuntu and on MSVC on Windows, runs the brute-force test suite, checks each demo program’s output against the output shown in this article, and repeats the tests under AddressSanitizer and UndefinedBehaviorSanitizer. The C workflow also confirms that AddressSanitizer reports the stack overflow in stack_table.c. A green badge means those checks passed on the latest commit; it does not cover inputs the tests do not generate.