Dynamic Programming II

def floyd_warshall(W):
    """
    All-pairs shortest paths on |V|-vertex graph.
    W[u][v] = weight of edge (u,v), or float('inf') if no edge.
    W[u][u] = 0 for all u.
    Returns dist[u][v] = delta(u,v), or -inf if negative cycle.
    O(|V|^3) time and space.
    """
    import copy
    V = len(W)
    d = copy.deepcopy(W)                    # d[u][v] = d(u,v,0)

    for k in range(V):                      # allow vertex k as intermediate
        for u in range(V):
            for v in range(V):
                # either don't use k, or go u->...->k->...->v
                via_k = d[u][k] + d[k][v]
                if via_k < d[u][v]:
                    d[u][v] = via_k

    # Detect negative cycles: if d[u][u] < 0, u is on a neg cycle
    for u in range(V):
        if d[u][u] < 0:
            raise ValueError(f"Negative-weight cycle detected through vertex {u}")
    return d

# Note: d[u][v] in-place update is correct because:
# d(u,v,k) = min(d(u,v,k-1), d(u,k,k-1) + d(k,v,k-1))
# After row/col k is fully settled, d[u][k] = d(u,k,k) = d(u,k,k-1)
# (vertex k cannot improve path to itself via itself if no neg cycle)
# so the in-place update computes the correct value.

def cut_rod(L, v):
    """
    Max value from rod of length L with piece values v[0..L].
    v[0]=0, v[l]=value of piece of length l. O(L^2).
    Returns (max_value, list_of_pieces).
    """
    x      = [0] * (L + 1)          # x[l] = max value for rod of length l
    parent = [None] * (L + 1)       # parent[l] = l - (first piece chosen)

    for l in range(1, L + 1):       # topological order: increasing l
        for piece in range(1, l + 1):
            candidate = v[piece] + x[l - piece]
            if candidate > x[l]:
                x[l]      = candidate
                parent[l] = l - piece    # remainder after cutting piece

    # Reconstruct cuts from parent pointers
    pieces, l = [], L
    while l > 0:
        piece = l - parent[l]        # piece length chosen at length l
        pieces.append(piece)
        l = parent[l]
    return x[L], pieces

# Example: L=7, v=[0,1,10,13,18,20,31,32]
# x[7] = 33 via pieces [2, 2, 3] (10+10+13=33)

def subset_sum(A, T):
    """
    Does any subset of A sum to exactly T?
    O(n*T) time and space (pseudopolynomial).
    """
    n = len(A)
    # x[i][t] = can subset of A[i:] sum to t
    # Space optimisation: only need current and next row -> O(T) space
    # Use 1D DP: x[t] = reachable with items A[i:]
    # Process items in reverse, update t in reverse to avoid using same item twice

    x = [False] * (T + 1)
    x[0] = True                        # base: empty subset sums to 0

    for item in A:                     # add one item at a time
        # Traverse t in reverse to avoid using item more than once
        for t in range(T, item - 1, -1):
            if x[t - item]:
                x[t] = True            # can reach t by adding item

    return x[T]

def subset_sum_with_trace(A, T):
    """Returns the actual subset, or None if impossible."""
    n = len(A)
    # Full 2D table for traceback
    x = [[False] * (T + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        x[i][0] = True                 # base: t=0 always reachable

    for i in range(n - 1, -1, -1):    # decreasing i (topo order)
        for t in range(1, T + 1):
            x[i][t] = x[i + 1][t]     # don't include A[i]
            if t >= A[i]:
                x[i][t] = x[i][t] or x[i + 1][t - A[i]]

    if not x[0][T]: return None

    # Traceback: find which items were included
    subset, t = [], T
    for i in range(n):
        if t >= A[i] and x[i + 1][t - A[i]]:
            subset.append(A[i])
            t -= A[i]
    return subset

# Example: A=[1,3,4,12,19,21,22], T=47 -> [3,4,19,21] sums to 47