Algorithm dossier

  • Category: DP
  • Worst-case complexity: O(n²)
  • Approach: DP
  • Data structure: Array
  • First formalised: 1950s

Why this snippet is 0/1 Knapsack

Why 0/1 knapsack DP. Two-axis table: rows index items, columns index capacity. The recurrence at f[i][c] is "either skip item i (take f[i-1][c]), or take it if it fits (f[i-1][c-w[i-1]] + v[i-1])." The 0/1 is the *take-it-or-leave-it* constraint — items aren't divisible. Linear-space optimisation. A 1D rolling array suffices because each row only depends on the previous row; this 2D version is the teaching shape.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.