# Algorithmus für perfekte Kombination



## seTT (18. Dez 2013)

Hey!

Vorweg möchte ich sagen, dass ich bei google einige Tipps gefunden habe, die meistens auf greedy-Algorithmen verwiesen haben. Da ich aber weder Informatiker bin noch große Ahnung vom Programmieren habe, versuche ich mein Glück nun hier:

Mein Problem ist folgendes:
Ich habe eine Menge an Rezepten, die die Herstellung von Gegenständen beschreibt.
Jeder Gegenstand benötigt eine feste Menge Ressourcen und wirft einen Gewinn ab.
Es soll nun die Menge Gegenstände herausgefunden werden, die den größten Gewinn abwirft. Dabei können Gegenstände des selben Rezepts mehrfach vorkommen.

Im Grunde sieht es so aus:

```
//10 verschiedene Ressourcen, feste Grundmenge
public int ressources[10] = {50,50,100,80,80,10,50,200,200,20}
//hier 2 Beispielrezepte, 10 Ressourcenkosten, letzter Integer gibt den Gewinn an
public int recipe[2][11] = {{2,2,3,1,1,0,4,2,2,1,1000},{0,0,6,5,2,4,8,6,5,10,1300}}
```

Ich habe mich bereits an eine einfache Lösung gewagt, die im Brute-Force-Verfahren alle Möglichkeit durchkämmt, aber wie bekannt ist, benötigt der Algorithmus sehr lange bei einer großen Anzahl Rezepten.

Ich weiß, es ist viel verlangt und nicht unbedingt im Sinne des Forums, aber vielleicht hat jemand Lust und Laune mir einen schöneren Algorithmus zu posten/erklären.
Im Übrigen ist dies keine Hausaufgabe oder Ähnliches, lediglich reine Neugierde bezüglich der Optimierung in einem Spiel.


----------



## Ruzmanz (18. Dez 2013)

Schau mal nach dem Rucksackproblem, da wirst du bei Google einiges finden. Auch Java-Implementierungen.


----------



## rme (19. Dez 2013)

(Sorry, hatte die Aufgabenstellung erst falsch verstanden, dadurch ist dieser Post nicht mehr relevant)


----------

