dp[i][w] = max(dp[i-1][w], dp[i-1][w - peso[i]] + valor[i])

Itens: {peso: 2, valor: 3}, {peso: 3, valor: 4}, {peso: 4, valor: 5}, {peso: 5, valor: 6}
Capacidade W = 8

Tabela dp[i][w]:
       w=0  w=1  w=2  w=3  w=4  w=5  w=6  w=7  w=8
i=0     0    0    3    3    3    3    3    3    3
i=1     0    0    3    4    4    7    7    7    7
i=2     0    0    3    4    5    7    8    9    9
i=3     0    0    3    4    5    7    8    9   10

Resposta: dp[3][8] = 10 (itens 1, 2 e 3 com pesos 3+5=8... ou 2+3+5)

Rastreando: pegar item 3 (valor 6, peso 5) + item 0 (valor 3, peso 2)
            → peso total = 7, valor total = 9... melhor: itens 1+2+0

const std = @import("std");
const Allocator = std.mem.Allocator;

const Item = struct {
    peso: u32,
    valor: u32,
    nome: []const u8,
};

/// Knapsack 0/1 — cada item pode ser usado no máximo uma vez.
/// Retorna o valor máximo e os itens selecionados.
pub fn knapsack01(
    allocator: Allocator,
    itens: []const Item,
    capacidade: u32,
) !struct { valor_max: u32, selecionados: []usize } {
    const n = itens.len;
    const w: usize = capacidade;

    // dp[i][j] = valor máximo usando itens 0..i com capacidade j
    const dp = try allocator.alloc([]u32, n + 1);
    defer {
        for (dp) |row| allocator.free(row);
        allocator.free(dp);
    }

    for (dp) |*row| {
        row.* = try allocator.alloc(u32, w + 1);
        @memset(row.*, 0);
    }

    // Preenche a tabela
    for (1..n + 1) |i| {
        for (0..w + 1) |j| {
            dp[i][j] = dp[i - 1][j]; // não incluir item i-1
            if (itens[i - 1].peso <= j) {
                const com_item = dp[i - 1][j - itens[i - 1].peso] + itens[i - 1].valor;
                if (com_item > dp[i][j]) {
                    dp[i][j] = com_item;
                }
            }
        }
    }

    // Rastreia itens selecionados
    var lista = std.ArrayList(usize).init(allocator);
    var j: usize = w;
    var i: usize = n;
    while (i > 0) : (i -= 1) {
        if (dp[i][j] != dp[i - 1][j]) {
            try lista.append(i - 1);
            j -= itens[i - 1].peso;
        }
    }

    return .{
        .valor_max = dp[n][w],
        .selecionados = try lista.toOwnedSlice(),
    };
}

/// Knapsack ilimitado — cada item pode ser usado quantas vezes quiser.
pub fn knapsackIlimitado(
    allocator: Allocator,
    itens: []const Item,
    capacidade: u32,
) !u32 {
    const w: usize = capacidade;
    const dp = try allocator.alloc(u32, w + 1);
    defer allocator.free(dp);
    @memset(dp, 0);

    for (1..w + 1) |j| {
        for (itens) |item| {
            if (item.peso <= j) {
                dp[j] = @max(dp[j], dp[j - item.peso] + item.valor);
            }
        }
    }

    return dp[w];
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const itens = [_]Item{
        .{ .peso = 2, .valor = 3, .nome = "Livro" },
        .{ .peso = 3, .valor = 4, .nome = "Tablet" },
        .{ .peso = 4, .valor = 5, .nome = "Notebook" },
        .{ .peso = 5, .valor = 6, .nome = "Câmera" },
    };

    const capacidade: u32 = 8;

    // Knapsack 0/1
    const resultado = try knapsack01(allocator, &itens, capacidade);
    defer allocator.free(resultado.selecionados);

    try stdout.print("Mochila 0/1 (capacidade {d}):\n", .{capacidade});
    try stdout.print("Valor máximo: {d}\n", .{resultado.valor_max});
    try stdout.print("Itens selecionados:\n", .{});
    var peso_total: u32 = 0;
    for (resultado.selecionados) |idx| {
        try stdout.print("  - {s} (peso: {d}, valor: {d})\n", .{
            itens[idx].nome, itens[idx].peso, itens[idx].valor,
        });
        peso_total += itens[idx].peso;
    }
    try stdout.print("Peso total: {d}\n", .{peso_total});

    // Knapsack ilimitado
    const valor_ilimitado = try knapsackIlimitado(allocator, &itens, capacidade);
    try stdout.print("\nMochila ilimitada: valor máximo = {d}\n", .{valor_ilimitado});
}