Problema de la mochila (0/1)

nombre = ["agua", "libro", "linterna", "tablet"]
peso = [1, 3, 4, 5]
valor = [1, 4, 5, 7]
capacidad, n = 7, len(peso)

dp = [[0] * (capacidad + 1) for _ in range(n + 1)]   # dp[i][w]: lo mejor con los i primeros y w kg
for i in range(1, n + 1):
    for w in range(capacidad + 1):
        dp[i][w] = dp[i - 1][w]                       # sin el objeto i
        if peso[i - 1] <= w:                          # con él, si cabe
            dp[i][w] = max(dp[i][w], dp[i - 1][w - peso[i - 1]] + valor[i - 1])

print("kg:".ljust(10) + "".join(f"{w:3d}" for w in range(capacidad + 1)))
for i in range(n + 1):
    etiqueta = "-" if i == 0 else nombre[i - 1]
    print(etiqueta.ljust(10) + "".join(f"{dp[i][w]:3d}" for w in range(capacidad + 1)))

dentro = []
w = capacidad
for i in range(n, 0, -1):
    if dp[i][w] != dp[i - 1][w]:                      # distinto de la fila de arriba: entró
        dentro.insert(0, nombre[i - 1])
        w -= peso[i - 1]
print(f"Valor máximo: {dp[n][capacidad]} con {' y '.join(dentro)} ({capacidad - w} de {capacidad} kg)")

const nombre = ["agua", "libro", "linterna", "tablet"];
const peso = [1, 3, 4, 5];
const valor = [1, 4, 5, 7];
const capacidad = 7, n = peso.length;

const dp = Array.from({ length: n + 1 }, () => new Array(capacidad + 1).fill(0));   // dp[i][w]: lo mejor con los i primeros y w kg
for (let i = 1; i <= n; i++)
    for (let w = 0; w <= capacidad; w++) {
        dp[i][w] = dp[i - 1][w];                       // sin el objeto i
        if (peso[i - 1] <= w)                          // con él, si cabe
            dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - peso[i - 1]] + valor[i - 1]);
    }

let cabecera = "kg:".padEnd(10);
for (let w = 0; w <= capacidad; w++) cabecera += String(w).padStart(3);
console.log(cabecera);
for (let i = 0; i <= n; i++) {
    let fila = (i === 0 ? "-" : nombre[i - 1]).padEnd(10);
    for (let w = 0; w <= capacidad; w++) fila += String(dp[i][w]).padStart(3);
    console.log(fila);
}

const dentro = [];
let w = capacidad;
for (let i = n; i > 0; i--)
    if (dp[i][w] !== dp[i - 1][w]) {                   // distinto de la fila de arriba: entró
        dentro.unshift(nombre[i - 1]);
        w -= peso[i - 1];
    }
console.log(`Valor máximo: ${dp[n][capacidad]} con ${dentro.join(" y ")} (${capacidad - w} de ${capacidad} kg)`);

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        string[] nombre = { "agua", "libro", "linterna", "tablet" };
        int[] peso = { 1, 3, 4, 5 };
        int[] valor = { 1, 4, 5, 7 };
        int capacidad = 7, n = peso.Length;

        int[,] dp = new int[n + 1, capacidad + 1];           // dp[i, w]: lo mejor con los i primeros y w kg
        for (int i = 1; i <= n; i++)
            for (int w = 0; w <= capacidad; w++) {
                dp[i, w] = dp[i - 1, w];                       // sin el objeto i
                if (peso[i - 1] <= w)                          // con él, si cabe
                    dp[i, w] = Math.Max(dp[i, w], dp[i - 1, w - peso[i - 1]] + valor[i - 1]);
            }

        string cabecera = "kg:".PadRight(10);
        for (int w = 0; w <= capacidad; w++) cabecera += w.ToString().PadLeft(3);
        Console.WriteLine(cabecera);
        for (int i = 0; i <= n; i++) {
            string fila = (i == 0 ? "-" : nombre[i - 1]).PadRight(10);
            for (int w = 0; w <= capacidad; w++) fila += dp[i, w].ToString().PadLeft(3);
            Console.WriteLine(fila);
        }

        var dentro = new List<string>();
        int kg = capacidad;
        for (int i = n; i > 0; i--)
            if (dp[i, kg] != dp[i - 1, kg]) {                 // distinto de la fila de arriba: entró
                dentro.Insert(0, nombre[i - 1]);
                kg -= peso[i - 1];
            }
        Console.WriteLine(
quot;Valor máximo: {dp[n, capacidad]} con {string.Join(" y ", dentro)} ({capacidad - kg} de {capacidad} kg)");
    }
}

<?php
$nombre = ["agua", "libro", "linterna", "tablet"];
$peso = [1, 3, 4, 5];
$valor = [1, 4, 5, 7];
$capacidad = 7;
$n = count($peso);

$dp = array_fill(0, $n + 1, array_fill(0, $capacidad + 1, 0));   // $dp[i][w]: lo mejor con los i primeros y w kg
for ($i = 1; $i <= $n; $i++)
    for ($w = 0; $w <= $capacidad; $w++) {
        $dp[$i][$w] = $dp[$i - 1][$w];                 // sin el objeto i
        if ($peso[$i - 1] <= $w)                       // con él, si cabe
            $dp[$i][$w] = max($dp[$i][$w], $dp[$i - 1][$w - $peso[$i - 1]] + $valor[$i - 1]);
    }

$cabecera = sprintf("%-10s", "kg:");
for ($w = 0; $w <= $capacidad; $w++) $cabecera .= sprintf("%3d", $w);
echo $cabecera . "\n";
for ($i = 0; $i <= $n; $i++) {
    $fila = sprintf("%-10s", $i == 0 ? "-" : $nombre[$i - 1]);
    for ($w = 0; $w <= $capacidad; $w++) $fila .= sprintf("%3d", $dp[$i][$w]);
    echo $fila . "\n";
}

$dentro = [];
$w = $capacidad;
for ($i = $n; $i > 0; $i--)
    if ($dp[$i][$w] != $dp[$i - 1][$w]) {              // distinto de la fila de arriba: entró
        array_unshift($dentro, $nombre[$i - 1]);
        $w -= $peso[$i - 1];
    }
echo "Valor máximo: {$dp[$n][$capacidad]} con " . implode(" y ", $dentro) . " (" . ($capacidad - $w) . " de $capacidad kg)\n";

from functools import cmp_to_key

PESO = [6, 3, 4, 2]
VALOR = [30, 14, 16, 9]
CAPACIDAD = 10


def voraz():
    """Voraz: por orden de €/kg, cada objeto que quepa. Rápido, pero en la mochila 0/1 puede fallar."""
    orden = sorted(range(4), key=cmp_to_key(lambda a, b: VALOR[b] * PESO[a] - VALOR[a] * PESO[b]))   # más €/kg primero, sin decimales
    libre, total = CAPACIDAD, 0
    for i in orden:
        if PESO[i] <= libre:
            libre -= PESO[i]
            total += VALOR[i]
    return total


def fuerza_bruta():
    """Fuerza bruta: cada número de 0 a 2^n − 1 es un subconjunto (el bit k dice si el objeto k entra)."""
    mejor, n = 0, len(PESO)
    for mascara in range(1 << n):
        p = v = 0
        for k in range(n):
            if mascara & (1 << k):
                p += PESO[k]
                v += VALOR[k]
        if p <= CAPACIDAD:
            mejor = max(mejor, v)
    return mejor


def tabla():
    """La tabla con una sola fila: w de mayor a menor, para no usar un objeto dos veces."""
    dp = [0] * (CAPACIDAD + 1)
    for i in range(len(PESO)):
        for w in range(CAPACIDAD, PESO[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - PESO[i]] + VALOR[i])
    return dp[CAPACIDAD]


print(f"Voraz por €/kg: {voraz()}")
print(f"Fuerza bruta, {1 << len(PESO)} subconjuntos: {fuerza_bruta()}")
print(f"Tabla de una fila, {CAPACIDAD + 1} casillas: {tabla()}")
print("El voraz coge 6 kg + 3 kg (44) y ya no le cabe nada; lo mejor es 6 kg + 4 kg (46).")

const PESO = [6, 3, 4, 2];
const VALOR = [30, 14, 16, 9];
const CAPACIDAD = 10;

/** Voraz: por orden de €/kg, cada objeto que quepa. Rápido, pero en la mochila 0/1 puede fallar. */
function voraz() {
    const orden = [0, 1, 2, 3].sort((a, b) => VALOR[b] * PESO[a] - VALOR[a] * PESO[b]);   // más €/kg primero, sin decimales
    let libre = CAPACIDAD, total = 0;
    for (const i of orden)
        if (PESO[i] <= libre) {
            libre -= PESO[i];
            total += VALOR[i];
        }
    return total;
}

/** Fuerza bruta: cada número de 0 a 2^n − 1 es un subconjunto (el bit k dice si el objeto k entra). */
function fuerzaBruta() {
    let mejor = 0;
    const n = PESO.length;
    for (let mascara = 0; mascara < (1 << n); mascara++) {
        let p = 0, v = 0;
        for (let k = 0; k < n; k++)
            if (mascara & (1 << k)) {
                p += PESO[k];
                v += VALOR[k];
            }
        if (p <= CAPACIDAD) mejor = Math.max(mejor, v);
    }
    return mejor;
}

/** La tabla con una sola fila: w de mayor a menor, para no usar un objeto dos veces. */
function tabla() {
    const dp = new Array(CAPACIDAD + 1).fill(0);
    for (let i = 0; i < PESO.length; i++)
        for (let w = CAPACIDAD; w >= PESO[i]; w--)
            dp[w] = Math.max(dp[w], dp[w - PESO[i]] + VALOR[i]);
    return dp[CAPACIDAD];
}

console.log(`Voraz por €/kg: ${voraz()}`);
console.log(`Fuerza bruta, ${1 << PESO.length} subconjuntos: ${fuerzaBruta()}`);
console.log(`Tabla de una fila, ${CAPACIDAD + 1} casillas: ${tabla()}`);
console.log("El voraz coge 6 kg + 3 kg (44) y ya no le cabe nada; lo mejor es 6 kg + 4 kg (46).");

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static readonly int[] PESO = { 6, 3, 4, 2 };
    static readonly int[] VALOR = { 30, 14, 16, 9 };
    const int CAPACIDAD = 10;

    /// Voraz: por orden de €/kg, cada objeto que quepa. Rápido, pero en la mochila 0/1 puede fallar.
    static int Voraz() {
        var orden = new[] { 0, 1, 2, 3 }.OrderBy(i => i, Comparer<int>.Create((a, b) => VALOR[b] * PESO[a] - VALOR[a] * PESO[b]));   // más €/kg primero
        int libre = CAPACIDAD, total = 0;
        foreach (int i in orden)
            if (PESO[i] <= libre) {
                libre -= PESO[i];
                total += VALOR[i];
            }
        return total;
    }

    /// Fuerza bruta: cada número de 0 a 2^n − 1 es un subconjunto (el bit k dice si el objeto k entra).
    static int FuerzaBruta() {
        int mejor = 0, n = PESO.Length;
        for (int mascara = 0; mascara < (1 << n); mascara++) {
            int p = 0, v = 0;
            for (int k = 0; k < n; k++)
                if ((mascara & (1 << k)) != 0) {
                    p += PESO[k];
                    v += VALOR[k];
                }
            if (p <= CAPACIDAD) mejor = Math.Max(mejor, v);
        }
        return mejor;
    }

    /// La tabla con una sola fila: w de mayor a menor, para no usar un objeto dos veces.
    static int Tabla() {
        int[] dp = new int[CAPACIDAD + 1];
        for (int i = 0; i < PESO.Length; i++)
            for (int w = CAPACIDAD; w >= PESO[i]; w--)
                dp[w] = Math.Max(dp[w], dp[w - PESO[i]] + VALOR[i]);
        return dp[CAPACIDAD];
    }

    static void Main() {
        Console.WriteLine("Voraz por €/kg: " + Voraz());
        Console.WriteLine("Fuerza bruta, " + (1 << PESO.Length) + " subconjuntos: " + FuerzaBruta());
        Console.WriteLine("Tabla de una fila, " + (CAPACIDAD + 1) + " casillas: " + Tabla());
        Console.WriteLine("El voraz coge 6 kg + 3 kg (44) y ya no le cabe nada; lo mejor es 6 kg + 4 kg (46).");
    }
}

<?php
const PESO = [6, 3, 4, 2];
const VALOR = [30, 14, 16, 9];
const CAPACIDAD = 10;

/** Voraz: por orden de €/kg, cada objeto que quepa. Rápido, pero en la mochila 0/1 puede fallar. */
function voraz(): int {
    $orden = [0, 1, 2, 3];
    usort($orden, fn($a, $b) => VALOR[$b] * PESO[$a] - VALOR[$a] * PESO[$b]);   // más €/kg primero, sin decimales
    $libre = CAPACIDAD;
    $total = 0;
    foreach ($orden as $i)
        if (PESO[$i] <= $libre) {
            $libre -= PESO[$i];
            $total += VALOR[$i];
        }
    return $total;
}

/** Fuerza bruta: cada número de 0 a 2^n − 1 es un subconjunto (el bit k dice si el objeto k entra). */
function fuerzaBruta(): int {
    $mejor = 0;
    $n = count(PESO);
    for ($mascara = 0; $mascara < (1 << $n); $mascara++) {
        $p = 0;
        $v = 0;
        for ($k = 0; $k < $n; $k++)
            if ($mascara & (1 << $k)) {
                $p += PESO[$k];
                $v += VALOR[$k];
            }
        if ($p <= CAPACIDAD) $mejor = max($mejor, $v);
    }
    return $mejor;
}

/** La tabla con una sola fila: w de mayor a menor, para no usar un objeto dos veces. */
function tabla(): int {
    $dp = array_fill(0, CAPACIDAD + 1, 0);
    for ($i = 0; $i < count(PESO); $i++)
        for ($w = CAPACIDAD; $w >= PESO[$i]; $w--)
            $dp[$w] = max($dp[$w], $dp[$w - PESO[$i]] + VALOR[$i]);
    return $dp[CAPACIDAD];
}

echo "Voraz por €/kg: " . voraz() . "\n";
echo "Fuerza bruta, " . (1 << count(PESO)) . " subconjuntos: " . fuerzaBruta() . "\n";
echo "Tabla de una fila, " . (CAPACIDAD + 1) . " casillas: " . tabla() . "\n";
echo "El voraz coge 6 kg + 3 kg (44) y ya no le cabe nada; lo mejor es 6 kg + 4 kg (46).\n";