Chapter XVIII Knapsack

DP in C#

The textbook 0-1 DP, in C# with LINQ for the reconstruction step. .NET's value semantics make the table easy to reason about.

Define an Item record. C#'s positional records are perfect for value-typed data shapes — Equatable, Hashable, and a deconstructor for free.

public record Item(int Weight, int Value);

public class Knapsack {
    public static (int value, IEnumerable<int> picked)
        Solve(IList<Item> items, int capacity) { ... }
}

Build the DP table dp[i, w] = best value using first i items with capacity w. The classic recurrence: take or leave the i-th item.

int n = items.Count;
var dp = new int[n + 1, capacity + 1];
for (int i = 1; i <= n; i++) {
    var (wi, vi) = (items[i-1].Weight, items[i-1].Value);
    for (int w = 0; w <= capacity; w++) {
        dp[i, w] = dp[i - 1, w];
        if (wi <= w)
            dp[i, w] = Math.Max(dp[i, w], dp[i - 1, w - wi] + vi);
    }
}

Walk back through the table to reconstruct which items got picked. If dp[i, w] > dp[i-1, w], item i was taken. LINQ's Reverse turns the descending walk into an ascending list.

var picked = new List<int>();
int rem = capacity;
for (int i = n; i >= 1; i--) {
    if (dp[i, rem] != dp[i - 1, rem]) {
        picked.Add(i - 1);
        rem -= items[i - 1].Weight;
    }
}
return (dp[n, capacity], picked.AsEnumerable().Reverse());

04

Drive it. For 1000 items and capacity 10⁶, this DP runs in well under a second on commodity hardware. For really enormous capacity, you switch to branch-and-bound with LP relaxation bounds — but most problems are this size.
```
var items = new List<Item> {
    new(2, 3), new(3, 4), new(4, 5), new(5, 6)
};
var (val, picked) = Knapsack.Solve(items, 5);
Console.WriteLine($"value={val}, picked={string.Join(",", picked)}");
// value=7, picked=0,1
```

Grammar — C#

C# is a value-and-reference language with serious type-system muscle: positional records for immutable shapes, LINQ for fluent collection queries, generics with variance. Knapsack DP fits the language idiomatically.

public record T(int A, int B): positional record — a compact immutable class with synthesized constructor, equality, deconstruction, and ToString.
using System.Linq;: enables LINQ extension methods on collections. Almost always wanted.
var x = ...;: type-inferred local. Compiler picks the type from the right-hand side.
int[,]: 2D array type. `new int[n, m]` allocates; index with `arr[i, j]`.
IList<T>: an interface for list-like collections. Use it as the parameter type for flexibility.
IEnumerable<T>: the lazy-iteration interface. LINQ's native return type.
.Select(...).Where(...).Reverse(): LINQ pipeline — fluent transformation. Each call returns a new IEnumerable; the work happens lazily.
Console.WriteLine($"{x}"): interpolated string — embed expressions inside `$"..."` with `{expr}`.
Math.Max(a, b): standard math. Most utilities live in the System.Math static class.

An item is a small immutable record of weight and value. The positional-record syntax replaces fifty lines of class boilerplate (constructor, properties, Equals, GetHashCode, ToString) with one.

public record Item(int Weight, int Value);

var items = new List<Item> {
    new(2, 3), new(3, 4), new(4, 5)
};

// LINQ over the records:
var total = items.Sum(i => i.Value);  // 12
var heavy = items.Where(i => i.Weight >= 3).ToList();

.NET Fiddle — try C# in your browser →