{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DS 26/27 – Vertiefung am Beispiel: Das Rucksackproblem\n",
    "**Informatik 10 – MINT-Zweig | Informatisches Problemlösen**\n",
    "\n",
    "## Lernziel\n",
    "Ich wende Brute-Force- und Greedy-Ansätze auf ein neues Beispielproblem (Rucksackproblem) an und vergleiche beide Strategien."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "sprachhilfe"
    ]
   },
   "source": [
    "## 🗣️ Sprachhilfe\n",
    "- „Es handelt sich um ein Problem/eine Probleminstanz, weil …“\n",
    "- „Der Ansatz prüft/wählt … und benötigt dabei …“\n",
    "- „Die Heuristik ist hier geeignet/nicht geeignet, weil …“"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📌 Merksätze\n",
    "\n",
    "- Beim **Rucksackproblem (Knapsack Problem)** stehen mehrere Gegenstände mit jeweils einem **Gewicht** und einem **Wert** zur Verfügung. Gesucht ist die Auswahl von Gegenständen mit **maximalem Gesamtwert**, deren **Gesamtgewicht** eine vorgegebene Tragkraft nicht übersteigt.\n",
    "- **Brute-Force-Ansatz:** Alle möglichen **Teilmengen** der Gegenstände werden gebildet und bewertet – bei `n` Gegenständen gibt es `2^n` Teilmengen (**exponentieller Aufwand**).\n",
    "- **Greedy-Heuristik:** Die Gegenstände werden nach ihrem **Wert-Gewicht-Verhältnis** (Wert ÷ Gewicht) sortiert und **so lange** eingepackt, bis kein weiterer Gegenstand mehr hineinpasst."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 💡 Probleminstanz\n",
    "Rucksack-Tragkraft: **10 kg**\n",
    "\n",
    "| Gegenstand | Gewicht (kg) | Wert (€) |\n",
    "|---|---|---|\n",
    "| Zelt | 5 | 60 |\n",
    "| Schlafsack | 4 | 40 |\n",
    "| Kocher | 2 | 30 |\n",
    "| Proviant | 3 | 25 |\n",
    "| Erste-Hilfe-Set | 1 | 20 |\n",
    "\n",
    "**Aufgabe zum Einstieg (von Hand):** Findet durch Ausprobieren mindestens zwei zulässige Kombinationen (Gesamtgewicht ≤ 10 kg) und berechnet jeweils den Gesamtwert."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Eure Kombinationen und Werte hier)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🐍 Brute-Force-Lösung"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "gegenstaende = [\n",
    "    (\"Zelt\", 5, 60),\n",
    "    (\"Schlafsack\", 4, 40),\n",
    "    (\"Kocher\", 2, 30),\n",
    "    (\"Proviant\", 3, 25),\n",
    "    (\"Erste-Hilfe-Set\", 1, 20),\n",
    "]\n",
    "tragkraft = 10\n",
    "\n",
    "beste_kombination = None\n",
    "bester_wert = 0\n",
    "\n",
    "for r in range(len(gegenstaende) + 1):\n",
    "    for kombination in combinations(gegenstaende, r):\n",
    "        gesamtgewicht = sum(g[1] for g in kombination)\n",
    "        gesamtwert = sum(g[2] for g in kombination)\n",
    "        if gesamtgewicht <= tragkraft and gesamtwert > bester_wert:\n",
    "            bester_wert = gesamtwert\n",
    "            beste_kombination = kombination\n",
    "\n",
    "print(\"Optimale Kombination:\", [g[0] for g in beste_kombination])\n",
    "print(\"Gesamtwert:\", bester_wert)\n",
    "print(\"Gesamtgewicht:\", sum(g[1] for g in beste_kombination))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 1 – Anzahl der Teilmengen\n",
    "Wie viele Teilmengen müssen bei `n` Gegenständen geprüft werden? Berechnet dies für die vorliegende Instanz mit `2^n` und begründet das Ergebnis. Die folgende Code-Zelle kann optional zur Kontrolle ergänzt werden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# OPTIONAL: Zähler für geprüfte Teilmengen zur Kontrolle ergänzen\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 2 – Greedy-Heuristik von Hand anwenden\n",
    "Berechnet für jeden Gegenstand das **Wert-Gewicht-Verhältnis**, sortiert die Gegenstände danach absteigend und packt sie in dieser Reihenfolge, sofern sie noch passen. Vergleicht das Ergebnis mit der optimalen Brute-Force-Lösung. Haltet jeden Auswahlschritt in einer Tabelle fest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# OPTIONAL: Greedy-Heuristik für das Rucksackproblem programmieren\n",
    "\n",
    "def greedy_rucksack(gegenstaende, tragkraft):\n",
    "    # Tipp: sortiert(gegenstaende, key=lambda g: g[2]/g[1], reverse=True)\n",
    "    pass\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 3 – Grenzen der Heuristik\n",
    "Überlegt euch (oder konstruiert) eine Probleminstanz, bei der die Greedy-Heuristik **nicht** die optimale Lösung findet. Testet eure Instanz mit beiden Ansätzen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# OPTIONAL: Gegenbeispiel-Instanz programmatisch testen\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11"
  },
  "v3_revision": {
   "basis": "MINT-Lehrplan Informatik 10 (2026)",
   "didaktik": "fragend-entwickelnder Kern, kurzer Transfer, flexible Reserve",
   "lerngruppe": "11 SuS"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
