Teilmengenproblem

{a,b,c}

{{a,b,c},{a},{b},{c},{a,b},{a,c},{b,c},{}}

http://www.nostalgie-games.de

KnapSack-Problem (0-1-Problem)

n Objekte Xi € G mit Massen mi (i € [1, N]) und Werten Wi werden in einen Rucksack mit Kapazität M.
Gesucht ist Füllung mit max. Gewinn (∑i Wi maximal)

Beispiel: M=30kg
WarenNr | 1 2 3 4 |
Masse | 15 25 10 20 | kg
Wert | 15 50 40 60 | €
*Spez.Wert | 1 2 4 3 | €/kg

greedy(wert): (4) + (3) => Wert: 100 //+backtracking
greedy(masse): (2) + % => Masse: 50
backtr(masse): (4) + (3) => : 100
greedy(spez.Wert): (3) + (4) : 100

Beispiel:
Nr | 1 2 3 4 5
m | 15 25 10 8 7
W | 45 50 40 28 28
W/m | 3 2 4 3,5 4

greedy(wert): (2) => wert: 50
greedy(masse): (2) => wert: 50
greedy(spez.wert): (3) + (5) + (4) => wert: 96

... kein Bock mehr...