0/1 Knapsack & subset sum

Overview

The 0/1 knapsack maximises the value you can carry within a weight capacity when each item may be taken at most once. The textbook table is 2-D — items × capacity — but it collapses to a single array indexed by capacity, and that collapse comes with the most important rule in this track: iterate capacity downward. Going upward would let the same item be picked twice (that is the unbounded knapsack, and exactly what coin change wanted). Subset-sum is the same algorithm with booleans instead of values: can any subset hit this target?

Why it matters

Knapsack is the archetype for constrained selection — budget allocation, cargo loading, choosing which jobs to run under a resource cap, selecting features under a size limit. And the downward-iteration rule is the kind of one-line detail that silently produces plausible-but-wrong answers: the code runs, the numbers look reasonable, and items have been used twice.

Core concepts

The recurrence. For item i with weight w and value v: dp[cap] = max(dp[cap], dp[cap - w] + v). Take it or leave it — the best of the two.

Why downward. In the 1-D array, dp[cap - w] must refer to the state before item i was considered. Iterating capacity from high to low guarantees that, because the smaller index has not been updated yet in this pass. Iterating upward means dp[cap-w] may already include item i, so it gets taken again — silently turning 0/1 into unbounded.

Unbounded on purpose. If items may repeat, iterate upward. The direction is the only difference between the two problems, which is worth internalising.

Subset sum. Replace values with reachability: dp[s] = dp[s] || dp[s - a[i]], again descending. dp[0] = 1 because the empty subset always reaches zero.

Space. The 1-D form is O(capacity) memory instead of O(items × capacity) — a large practical difference — but it discards the information needed to reconstruct which items were chosen. Keep the 2-D table if you need the selection, not just the score.

Complexity. O(n × capacity) time. That is pseudo-polynomial: it scales with the numeric capacity, not with the input's bit length, so a huge capacity is expensive even with few items.

Syntax notes

#include <stdlib.h>

int knapsack(const int *w, const int *v, int n, int cap) {
    int *dp = calloc((size_t)cap + 1, sizeof *dp);   // dp[c] = best value within capacity c
    if (!dp) return -1;
    for (int i = 0; i < n; i++)
        for (int c = cap; c >= w[i]; c--)            // DOWNWARD: each item used at most once
            if (dp[c - w[i]] + v[i] > dp[c])
                dp[c] = dp[c - w[i]] + v[i];
    int r = dp[cap];
    free(dp);
    return r;
}

/* subset sum: same shape, reachability instead of value */
int subset_sum(const int *a, int n, int t) {
    char *dp = calloc((size_t)t + 1, 1);
    if (!dp) return -1;
    dp[0] = 1;                                        // empty subset reaches 0
    for (int i = 0; i < n; i++)
        for (int s = t; s >= a[i]; s--)               // DOWNWARD again
            if (dp[s - a[i]]) dp[s] = 1;
    int r = dp[t];
    free(dp);
    return r;
}

Key points:

• Downward for 0/1, upward for unbounded — the entire difference.
• c >= w[i] as the loop bound removes any need for a separate negative-index check.
• calloc matters: an unvisited capacity must start at 0 (or false).

Lesson

The 0/1 knapsack maximizes value under a weight budget with each item usable once; subset sum is its boolean cousin. Both use a 1-D table swept downward over capacity — that downward direction is exactly what prevents reusing an item within the same pass.

Code examples

#include <stdio.h>
#include <stdlib.h>
static int knapsack(const int *w,const int *v,int n,int cap){ int *dp=calloc(cap+1,sizeof(int)); for(int i=0;i<n;i++)for(int c=cap;c>=w[i];c--)if(dp[c-w[i]]+v[i]>dp[c])dp[c]=dp[c-w[i]]+v[i]; int r=dp[cap]; free(dp); return r; }
static int subset_sum(const int *a,int n,int t){ char *dp=calloc(t+1,1); dp[0]=1; for(int i=0;i<n;i++)for(int s=t;s>=a[i];s--)if(dp[s-a[i]])dp[s]=1; int r=dp[t]; free(dp); return r; }
int main(void){
    int w[]={1,3,4,5}, v[]={1,4,5,7};
    printf("max value in a knapsack of capacity 7 = %d\n", knapsack(w,v,4,7));
    int a[]={3,34,4,12,5,2};
    printf("subset summing to 9? %s\n", subset_sum(a,6,9)?"yes":"no");
    return 0;
}

Line by line

Common mistakes

Sweeping capacity upward (turns 0/1 into unbounded, reusing items).

Debugging tips

Compiler errors and warnings:

• warning: implicit conversion loses integer precision when mixing int and size_t at the allocation; cast explicitly.
• Nothing warns about the loop direction — this bug is invisible to the compiler.

Runtime symptoms:

• The value is too high and an item was clearly used twice. You iterated capacity upward. This is the signature bug; flip to for (c = cap; c >= w[i]; c--).
• Segfault or garbage. The loop ran below w[i], indexing negatively — use c >= w[i] as the condition.
• Everything is zero. dp[0] = 1 missing in subset-sum, or values/weights swapped in the call.
• Correct answer, wrong item list. The 1-D table cannot reconstruct the selection; you need the 2-D table for that.
• Extremely slow for a big capacity. Expected — the algorithm is pseudo-polynomial in the capacity.

Technique: test with a single item that fits twice — w={2}, v={3}, cap=5. The 0/1 answer is 3; if you get 6 or 7, your loop runs the wrong way.

Memory safety

• Allocation size. (size_t)cap + 1 — validate that cap >= 0 first. A negative capacity casts to an enormous size_t and the allocation either fails or succeeds at a size you did not intend.
• Check the return. calloc can fail; the code above returns -1 rather than dereferencing NULL.
• Zero-initialisation is required. Both tables are read before every position is written, so calloc (not malloc) is correct here.
• Free on all paths — capture the result, free, then return; never return dp[cap] after freeing.
• Validate item weights. A zero or negative weight breaks the c >= w[i] invariant and can cause an infinite-looking loop or a negative index. Reject them at the boundary.
• Value overflow. Summed values can exceed int for large inputs; widen the accumulator if the data warrants it.

Real-world uses

Concrete uses: Cargo and container loading. Selecting which advertisements fit a slot budget. Choosing which features fit a firmware size limit. Portfolio selection under a spend cap. Cutting-stock and resource-allocation planning. Subset-sum underlies partition problems and appears in cryptanalysis of knapsack-based ciphers.

Professional best practices:

Beginner:

• Write a comment stating whether items may repeat, then pick the loop direction to match.
• Test the single-item-fits-twice case before trusting the implementation.

Intermediate:

• Use the 1-D form for the score, the 2-D form when you must report the chosen items.
• Remember the complexity is pseudo-polynomial; for very large capacities consider a different formulation (e.g. by value) or an approximation.
• Validate weights and capacity at the API boundary — the inner loops assume they are sane.

Practice tasks

1. (Beginner) 0/1 knapsack. Implement int knapsack(const int *w, const int *v, int n, int cap) with the 1-D descending loop. Example: w={2,3}, v={3,4}, cap=5 → 7. Concepts: take-or-leave recurrence, loop direction.

2. (Beginner) Prove the direction matters. Run the same input with an ascending inner loop and show the inflated result. Example: w={2}, v={3}, cap=5 → 3 descending, 6 ascending. Concepts: 0/1 vs unbounded.

3. (Intermediate) Subset sum. Implement int subset_sum(const int *a, int n, int t). Example: {3,34,4,12,5,2}, target 9 → 1 (4+5); target 30 → 0. Concepts: reachability DP.

4. (Intermediate) Reconstruct the chosen items. Use a 2-D table to report which items make the optimum, not just its value. Hint: walk backwards comparing dp[i][c] with dp[i-1][c]. Concepts: DP reconstruction, the space/information trade-off.

Summary

The 0/1 knapsack maximises value under a capacity with each item used at most once: dp[cap] = max(dp[cap], dp[cap-w] + v), collapsed to a single capacity-indexed array. The rule that makes it correct is iterating capacity downward, so dp[cap-w] still refers to the state before the current item — iterate upward and you have written the unbounded knapsack instead, silently reusing items. Subset-sum is the same loop with booleans and dp[0] = 1. The 1-D form gives the score in O(capacity) space; keep the 2-D table when you need to know which items were chosen.

Practice with these exercises

• 0/1 Knapsack
• Subset sum