algo-knapsack-01-dp

Answer

"""
0/1 Knapsack — Dynamic Programming
===================================
Two approaches: top-down memoization and bottom-up DP.
Both return (max_value, selected_indices) where selected_indices lists
the original indices (0-based) of items chosen for the optimal knapsack.
"""

from functools import lru_cache
from typing import List, Tuple


# ── 1. Bottom-Up DP (2D table) ──────────────────────────

def knapsack_bottom_up(weights: List[int], values: List[int],
                       capacity: int) -> Tuple[int, List[int]]:
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w_i, v_i = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            if w_i > c:
                dp[i][c] = dp[i - 1][c]
            else:
                dp[i][c] = max(dp[i - 1][c],
                               dp[i - 1][c - w_i] + v_i)

    # Reconstruct selected items
    selected, c = [], capacity
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:        # item i-1 was taken
            selected.append(i - 1)
            c -= weights[i - 1]
    selected.reverse()
    return dp[n][capacity], selected


# ── 2. Bottom-Up DP (1D space, O(W)) ───────────────────

def knapsack_bottom_up_1d(weights: List[int], values: List[int],
                          capacity: int) -> Tuple[int, List[int]]:
    n = len(weights)
    dp = [0] * (capacity + 1)
    keep = [[False] * (capacity + 1) for _ in range(n)]

    for i in range(n):
        w_i, v_i = weights[i], values[i]
        for c in range(capacity, w_i - 1, -1):       # backwards!
            take = dp[c - w_i] + v_i
            if take > dp[c]:
                dp[c] = take
                keep[i][c] = True

    selected, c = [], capacity
    for i in range(n - 1, -1, -1):
        if keep[i][c]:
            selected.append(i)
            c -= weights[i]
    selected.reverse()
    return dp[capacity], selected


# ── 3. Top-Down Memoization ────────────────────────────

def knapsack_top_down(weights: List[int], values: List[int],
                      capacity: int) -> Tuple[int, List[int]]:
    n = len(weights)

    @lru_cache(maxsize=None)
    def dp(i: int, cap: int) -> int:
        """Max value using items i..n-1 with capacity cap."""
        if i >= n or cap <= 0:
            return 0
        best = dp(i + 1, cap)                # skip
        if weights[i] <= cap:                # take (if fits)
            best = max(best, dp(i + 1, cap - weights[i]) + values[i])
        return best

    selected, cap = [], capacity
    for i in range(n):
        if weights[i] <= cap:
            without = dp(i + 1, cap)
            with_it = dp(i + 1, cap - weights[i]) + values[i]
            if with_it > without:            # strictly better → take it
                selected.append(i)
                cap -= weights[i]
    return dp(0, capacity), selected

Key ideas:

Reconstruction: Walk the decision table backwards. For bottom-up: whenever dp[i][c] ≠ dp[i-1][c], item i-1 was taken. For top-down: at each step, compare the value with vs without the item — if taking gives strictly more, it's selected.