The Knapsack Problem

import type { Tracer } from "../trace";import type { KnapsackProblem } from "./knapsack-problem";/** The most items the traced table takes: one row each, so the stage keeps every row readable. */export const KNAPSACK_TABLE_MAX_ITEMS = 6;/** The largest capacity the traced table takes: one column per unit, 0 to the capacity. */export const KNAPSACK_TABLE_MAX_CAPACITY = 12;/** The `take` of a cell whose item is heavier than the column's capacity. */export const KNAPSACK_NO_FIT = -1;export interface KnapsackReport {  capacity: number;  /** The best value any fitting choice reaches: the last row's last cell. */  best: number;  /** The items the traceback picked, in item order. */  chosen: string[];  /** What the chosen items weigh together. */  weight: number;  /** Table cells filled, one per item per capacity; the zero row is not counted. */  cells: number;  /** The value the ratio-greedy rule reaches on the same instance, for comparison. */  greedy: number;}/** * The 0/1 knapsack by a table of items against capacities. Each item * gets a row, each capacity from zero to the bag's limit a column, and * a cell holds the best value the first `i` items reach in a bag of * capacity `c`. That value is the better of two choices: skip the item, * which is the cell above, or take it, which is its value plus the cell * above at the capacity its weight leaves. An item heavier than the * column's capacity cannot be taken at all. A tie leaves the item out. * The zero row is the base case (no items, nothing to pack). The * answer sits in the last cell, and a walk back up the rows reads the * items out: where a cell differs from the one above it, the item was * taken and the capacity shrinks by its weight. * * Time: O(n * capacity), pseudo-polynomial since it grows with the * capacity's size, not its digit count. Space: O(n * capacity) for the * table. */export class Knapsack {  /** Rows 0..n, columns 0..capacity; row 0 is the zero row. */  private rows: number[][] = [];  constructor(    readonly problem: KnapsackProblem,    private readonly tracer?: Tracer,  ) {    if (problem.size > KNAPSACK_TABLE_MAX_ITEMS) throw new RangeError(`the traced table holds at most ${KNAPSACK_TABLE_MAX_ITEMS} items`);    if (problem.capacity > KNAPSACK_TABLE_MAX_CAPACITY) throw new RangeError(`the traced table holds a capacity of at most ${KNAPSACK_TABLE_MAX_CAPACITY}`);  }  /** The table as last filled: rows 0..n, columns 0..capacity; empty before `solve`. */  get table(): readonly (readonly number[])[] {    return this.rows.map((row) => [...row]);  }  /** Fills the table from the zero row down, then reads the chosen items back from the last cell. */  solve(): KnapsackReport {    const { capacity, items } = this.problem;    this.rows = [new Array<number>(capacity + 1).fill(0)];    // ▸ row 0 is the bag with no items offered: every capacity holds 0    this.tracer?.emit("base", { capacity });    let cells = 0;    items.forEach((item, i) => {      const index = i + 1;      // ▸ one row per item; its cells only ever look at the row above      this.tracer?.emit("item", { index, name: item.name, value: item.value, weight: item.weight });      cells += this.fill(index, item.weight, item.value);    });    const { chosen, weight } = this.traceback();    return {      capacity,      best: this.rows[items.length]![capacity]!,      chosen,      weight,      cells,      greedy: this.problem.greedy().value,    };  }  /** One row: for every capacity, the better of skipping the item (the cell above) and taking it (its value plus the cell above at what its weight leaves). */  private fill(index: number, weight: number, value: number): number {    const above = this.rows[index - 1]!;    const rowAbove = this.rows[index - 1]!;    const row: number[] = [];    for (let capacity = 0; capacity < above.length; capacity++) {    for (let capacity = 0; capacity < rowAbove.length; capacity++) {      const skip = above[capacity]!;      const valueIfSkipped = rowAbove[capacity]!;      const fits = weight <= capacity;      const take = fits ? value + above[capacity - weight]! : KNAPSACK_NO_FIT;      const valueIfTaken = fits ? value + rowAbove[capacity - weight]! : KNAPSACK_NO_FIT;      const taken = take > skip;      const taken = valueIfTaken > valueIfSkipped;      const best = taken ? take : skip;      const best = taken ? valueIfTaken : valueIfSkipped;      row.push(best);      // ▸ skip is the cell above; take is the item's value plus the cell above at what its weight leaves; keep the larger      this.tracer?.emit("cell", { best, capacity, fits, index, skip, take, taken });      this.tracer?.emit("cell", { best, capacity, fits, index, valueIfSkipped, valueIfTaken, taken });    }    this.rows.push(row);    return row.length;  }  /** From the last cell up: an item was taken where its row differs from the row above, and the capacity shrinks by its weight. */  private traceback(): { chosen: string[]; weight: number } {    const chosen: string[] = [];    let weight = 0;    let capacity = this.problem.capacity;    for (let index = this.problem.size; index >= 1; index--) {      const item = this.problem.items[index - 1]!;      const value = this.rows[index]![capacity]!;      const taken = value !== this.rows[index - 1]![capacity]!;      if (taken) {        chosen.push(item.name);        weight += item.weight;        capacity -= item.weight;      }      // ▸ from the last cell up: a row that differs from the one above took its item, and the capacity shrinks by its weight      this.tracer?.emit("backtrack", { capacity, index, name: item.name, taken, value });    }    return { chosen: chosen.reverse(), weight };  }}