#!/usr/bin/env python3

# Rucksack.py
"""
Kapitel MILP: Das Rucksackproblem (Knapsack).
Zeigt LP-Relaxation, Branch-and-Bound-Ergebnis und den Preis der Ganzzahligkeit
an einem Beispiel, das man vollstaendig im Kopf nachvollziehen kann.
"""

import numpy as np
from scipy.optimize import linprog

GEGENSTAENDE = ["Zelt", "Schlafsack", "Kocher", "Kamera", "Buch", "Wasserfilter", "Seil"]
NUTZEN =  np.array([40.0, 35.0, 20.0, 30.0,  8.0, 25.0, 12.0])
GEWICHT = np.array([ 6.0,  4.0,  3.0,  2.0,  1.0,  2.0,  3.0])
KAPAZITAET = 11.0        # kg


def loese(ganzzahlig: bool):
    n = len(NUTZEN)
    ergebnis = linprog(
        c=-NUTZEN, A_ub=[GEWICHT], b_ub=[KAPAZITAET],
        bounds=[(0, 1)] * n,                       # jedes Teil hoechstens einmal
        integrality=np.ones(n) if ganzzahlig else None,
        method="highs")
    return -ergebnis.fun, ergebnis.x


if __name__ == "__main__":
    z_lp, x_lp = loese(ganzzahlig=False)
    z_ip, x_ip = loese(ganzzahlig=True)

    print("=" * 72)
    print(f"  RUCKSACKPROBLEM  (Kapazitaet {KAPAZITAET:.0f} kg)")
    print("=" * 72)
    print(f"{'Gegenstand':<14} {'Nutzen':>7} {'kg':>5} {'Nutzen/kg':>10} "
          f"{'LP':>7} {'MILP':>6}")
    print("-" * 72)
    for i, name in enumerate(GEGENSTAENDE):
        # int(round(...)) statt Format "%.0f": vermeidet die Ausgabe "-0"
        print(f"{name:<14} {NUTZEN[i]:>7.0f} {GEWICHT[i]:>5.0f} "
              f"{NUTZEN[i]/GEWICHT[i]:>10.2f} {x_lp[i]:>7.2f} {int(round(x_ip[i])):>6d}")
    print("-" * 72)
    print(f"{'Gesamtnutzen':<14} {'':<7} {'':<5} {'':<10} {z_lp:>7.2f} {z_ip:>6.0f}")
    print(f"{'Gesamtgewicht':<14} {'':<7} {'':<5} {'':<10} "
          f"{GEWICHT @ x_lp:>7.2f} {GEWICHT @ x_ip:>6.0f}")
    print("-" * 72)
    print(f"Obere Schranke aus der LP-Relaxation: {z_lp:.2f}")
    print(f"Bestes ganzzahliges Ergebnis:         {z_ip:.0f}")
    print(f"Preis der Ganzzahligkeit:             {z_lp - z_ip:.2f} "
          f"({(1 - z_ip/z_lp)*100:.1f} %)")

    gebrochen = [GEGENSTAENDE[i] for i in range(len(NUTZEN)) if 1e-6 < x_lp[i] < 1 - 1e-6]
    print(f"\nIn der LP-Loesung nur teilweise eingepackt: {gebrochen}")
    print("Genau hier wuerde Branch-and-Bound verzweigen:")
    print(f"  Ast 1: {gebrochen[0]} bleibt ganz zuhause (x=0)")
    print(f"  Ast 2: {gebrochen[0]} kommt ganz mit    (x=1)")
    print("=" * 72)