Auf seinem Weg durch die Wüste kann ein Handelsreisender auf seinem Kamel Güter im Gesamtgewicht von 150kg transportieren. In seinem Handelskontor sind vor seiner Reise $n$ verschiedene Güter $x$ mit verschiedenem Gewicht $w(x)$ und unterschiedlichem Profit (bei Verkauf an Zielort) $p(x)$ vorhanden. Der Handelsreisende denkt über die folgenden drei möglichen Auswahlregeln für Güter nach:
(a) Wähle iterativ das Gut mit dem geringsten Gewicht bis kein Gut mehr auf das Kamel passt.
(b) Wähle iterativ das Gut (mit noch passendem Gewicht) mit dem höchsten Profit bis kein Gut mehr auf das Kamel passt.
(c) Wähle iterativ das Gut $x$ (mit noch passendem Gewicht) mit dem höchsten Verhältnis von Profit zu Gewicht ($p(x) / w(x)$) bis kein Gut mehr auf das Kamel passt.
Zeige, dass keine der drei Strategien im allgemeinen den möglichen Profit maximiert (also: es gibt $n$ Güter so, dass es eine Auswahl an Gütern gibt, die auf das Kamel passt und einen höheren Profit als die von der Auswahlregel gewählten Objekte ergibt). Zusatz: Kannst du auch $n$ Güter so wählen, das alle drei Regeln für diese Güter eine suboptimale Lösung geben?
