Servus Community,
Das Rucksackproblem versteh ich ja etwas. was mache ich aber wenn ich 2 unterschiedliche Begrenzungen habe.
Ich hätte das Beispiel ganz einfach mit dem Rucksackproblem gelöst und statt Gegenständen die BEstellungen genommen. Als maxGewicht wollte ich den Lagerplatz für die einzelnen Artikel nehmen, aber das sind ja 2 verschiedene Werte. Wie gehe ich da also vor?
mfg El Hadji
Das Rucksackproblem versteh ich ja etwas. was mache ich aber wenn ich 2 unterschiedliche Begrenzungen habe.
Ich hätte das Beispiel ganz einfach mit dem Rucksackproblem gelöst und statt Gegenständen die BEstellungen genommen. Als maxGewicht wollte ich den Lagerplatz für die einzelnen Artikel nehmen, aber das sind ja 2 verschiedene Werte. Wie gehe ich da also vor?
Code:
public class Rucksackproblem
{
public List<Gegenstand> getBesteAuswahl(List<Gegenstand> liste, double maxW) {
double bestValue = getBestValue(liste,maxW,0);
double restW = maxW;
double restV = bestValue;
ArrayList<Gegenstand> erg = new ArrayList<>();
for(int k=0; k<liste.size(); k++) {
//mit Gegenstaenden ab Index k kann restV erreicht werden, ohne restW zu überschreiten
if(getBestValue(liste,restW,k+1) < restV) {
Gegenstand g = liste.get(k);
erg.add(g);
restW -= g.weight;
restV -= g.value;
}
}
return erg;
}
/*
* Liefert den Wert der optimalen Auswahl von Gegenstaenden mit Index >=k.
*/
private double getBestValue(List<Gegenstand> liste, double maxW, int k) {
double erg = 0;
if(k == liste.size()) return erg;
Gegenstand g = liste.get(k);
if(g.weight <= maxW) {
erg = g.value + getBestValue(liste,maxW-g.weight,k+1);
}
double ergOhne = getBestValue(liste,maxW,k+1);
if(erg > ergOhne) {
return erg;
} else {
return ergOhne;
}
}
}
