Kamele beladen (Rekursion)
Ein Kamel soll optimal beladen werden. Das Kamel kann maximal 270 kg tragen. Aktuell sind Waren mit den folgenden Gewichten zu transportieren: 5, 18, 32, 34, 45, 57, 63, 69, 94, 98 und 121 kg. Nicht alle Gewichte müssen verwendet werden; die 270 kg sollen aber möglichst gut, wenn nicht sogar ganz ohne Rest beladen werden. Die Funktion
beladeOptimal(kapazitaet: integer, vorrat: integer[]): integer[]
erhält die maximal tragbare Last (kapazitaet) und eine Menge von aufzuteilenden Gewichten (vorrat). Das Resultat (hier integer[]) ist die Auswahl aus dem Vorrat, die der Belastbarkeit möglichst nahe kommt. Gehen Sie wie folgt rekursiv vor: Für jedes vorhandene Gewicht g aus dem Vorrat soll das Problem vereinfacht werden. Dazu wird dieses Gewicht probehalber aufgeladen:
tmpLadung: integer[]
tmpLadung := beladeOptimal(kapazitaet - g, "vorrat ohne g")
Danach wird das beste Resultat tmpLadung + g gesucht und als Array zurückgegeben. Behandeln Sie in der Methode beladeOptimal() zunächst die Abbruchbedingungen:
- Vorrat leer
- alle vorhandenen Gewichte sind zu schwer
- nur noch ein Gewicht im Vorrat
Zusatzaufgabe: Informieren Sie sich zu iterativen Lösungen zum "Rucksackproblem". Implementieren Sie diese Lösung für obiges Problem und diskutieren Sie die Lösung und den Lösungsweg.
0 Kommentare
3 Lösung(en)
public class KameleBeladen {
public static void main(String[] args) {
new KameleBeladen().top(); }
final int[] gegebeneGewichte = {5, 18, 32, 34, 45, 57, 63, 69, 94, 98, 121};
final int maximalKapazitaet = 270; // kg!
void top() {
int [] maximaleLoesung = beladeOptimal(maximalKapazitaet, gegebeneGewichte);
ausgeben(maximaleLoesung); }
int[] beladeOptimal(int kapazitaet, int[] gegebeneGewichte) {
// Rekursionsabbrüche:
// a) keine Gewichte vorhanden (Vorrat leer):
if(0 == gegebeneGewichte.length) {
return new int[] {}; }
// b) jedes Gewicht ist größer als die Kapazität:
boolean alleGroesser = alleGroesserAlsGegebeneKapazitaet(kapazitaet, gegebeneGewichte);
if(alleGroesser) {
return new int [] {}; }
// c) nur ein Gewicht gegeben, dieses ist <= maximalgewicht:
if(1 == gegebeneGewichte.length && gegebeneGewichte[0] <= kapazitaet) {
return new int[] {gegebeneGewichte[0]}; }
/* Rekursion mittels Vereinfachung:
* Entnehme jedes Gewicht, das kleiner als die Kapazität ist und schaue, wie
* nun optimal beladen wird. Das beste Resultat wird zurückgegeben.
*/
int [] maximaleBeladung = new int[] {};
int pMax = 0; // Welches Gewicht bewirkt die maximal mögliche Beladung.
for(int p : gegebeneGewichte){
if(p < kapazitaet) {
int [] aktuelleBeladungOhneP = beladeOptimal(kapazitaet - p, arrayOhneP(p, gegebeneGewichte));
if(beladungsGuete(aktuelleBeladungOhneP, kapazitaet - p) >= beladungsGuete(maximaleBeladung, kapazitaet - p)) {
maximaleBeladung = aktuelleBeladungOhneP;
pMax = p;
}
}
}
return arrayPlusP(maximaleBeladung, pMax); }
boolean alleGroesserAlsGegebeneKapazitaet(int kapazitaet, int[] gegebeneGewichte) {
boolean alleGroesser = true;
for(int g : gegebeneGewichte) {
if(g < kapazitaet) {
alleGroesser = false; }
}
return alleGroesser; }
/**
* Erzeuge ein neues Array, das pMag auch enthält.
*/
int[] arrayPlusP(int[] maximaleBeladung, int pMax) {
int[] res = new int[maximaleBeladung.length + 1];
int pos = 0;
while(pos < maximaleBeladung.length) {
res[pos] = maximaleBeladung[pos];
pos = pos + 1;
}
res[pos] = pMax;
return res; }
/**
* Je weniger frei bleibt, umso besser.
* Güte = negative Differenz zur kapazität;
*/
int beladungsGuete(int[] aktuelleBeladungOhneP, int kapazitaet) {
int baladungsSumme = arrSum(aktuelleBeladungOhneP);
return - (kapazitaet - baladungsSumme);}
/**
* Summe aller Zahlen im Array
*/
int arrSum(int[] aktuelleBeladungOhneP) {
int sum = 0;
for(int akt : aktuelleBeladungOhneP) {
sum = sum + akt; }
return sum; }
/*
* Erzeuge neues Array, bei dem das Gewicht p fehlt.
*/
int[] arrayOhneP(int p, int[] gegebeneGewichte) {
int [] res = new int[gegebeneGewichte.length - 1];
int pPos = findePositionVonPInArray(p, gegebeneGewichte);
elementPosAnsEndeTauschen(gegebeneGewichte, pPos);
int i = 0;
while(i < res.length) {
res[i] = gegebeneGewichte[i];
i = i + 1;
}
return res; }
/**
* Tausche das Element an Position pPos ans ende des Arrays.
*/
void elementPosAnsEndeTauschen(int[] arr, int pPos) {
int lastEle = arr[arr.length - 1];
int aktWert = arr[pPos];
arr[pPos] = lastEle;
arr[arr.length -1] = aktWert; }
int findePositionVonPInArray(int p, int[] gegebeneGewichte) {
int i = 0;
while(gegebeneGewichte[i] != p) {
i = i + 1;
}
return i; }
void ausgeben(int[] maximaleLoesung) {
System.out.println("Loesung: ");
for(int akt: maximaleLoesung) {
System.out.print(akt + " ");
}
System.out.println(" -> summe = " + arrSum(maximaleLoesung)); }
} // end of class KameleBeladen
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Kamele beladen
https://www.programmieraufgaben.ch/aufgabe/kamele-beladen/6gddr4zm
"""
# Programmieraufgabe:
# Ein Kamel soll optimal beladen werden. Das Kamel kann maximal 270 kg tragen.
# Aktuell sind Waren mit den folgenden Gewichten zu transportieren: 5, 18, 32,
# 34, 45, 57, 63, 69, 94, 98 und 121 kg. Nicht alle Gewichte müssen verwendet
# werden; die 270 kg sollen aber möglichst gut, wenn nicht sogar ganz ohne
# Rest beladen werden. Die Funktion
# beladeOptimal(kapazitaet: integer, vorrat: integer[]): integer[]
# erhält die maximal tragbare Last (kapazitaet) und eine Menge von
# aufzuteilenden Gewichten (vorrat). Das Resultat (hier integer[]) ist die
# Auswahl aus dem Vorrat, die der Belastbarkeit möglichst nahe kommt. Gehen
# Sie wie folgt rekursiv vor: Für jedes vorhandene Gewicht g aus dem Vorrat
# soll das Problem vereinfacht werden. Dazu wird dieses Gewicht probehalber
# aufgeladen:
# tmpLadung: integer[]
# tmpLadung := beladeOptimal(kapazitaet - g, "vorrat ohne g")
# Danach wird das beste Resultat tmpLadung + g gesucht und als Array
# zurückgegeben. Behandeln Sie in der Methode beladeOptimal() zunächst die
# Abbruchbedingungen:
# Vorrat leer
# alle vorhandenen Gewichte sind zu schwer
# nur noch ein Gewicht im Vorrat
#
# Autor, Erstellung:
# Ulrich Berntien, 2018-06-08
#
# Sprache:
# Python 3.6.6
from typing import *
def optimal_load(capacity: int, pool: Tuple[int, ...]) -> Tuple[int, ...]:
"""
Suche eine optimale Beladung.
Optimal ist eine Beladung, wenn die Kapazität möglichst weitgehend verwendet wird.
:param capacity: Bis zu dieser Grenze sollen Elemente aus dem pool genommen werden.
:param pool: Aus diesem Pool können Elemente genommen werden.
:return: Die Elemente der optimalen Beladung.
"""
tmp_optimal_load: int = 0
tmp_optimal_bag: Tuple[int, ...] = tuple()
for index in range(len(pool)):
if pool[index] <= capacity:
bag = optimal_load(capacity - pool[index], pool[0:index] + pool[index + 1:])
total = sum(bag) + pool[index]
if total > tmp_optimal_load:
tmp_optimal_load = total
tmp_optimal_bag = pool[index:index + 1] + bag
assert sum(tmp_optimal_bag) <= capacity
assert all(x in pool for x in tmp_optimal_bag)
return tmp_optimal_bag
camel_capacity = 270
camel_pool = (5, 18, 32, 34, 45, 57, 63, 69, 94, 98, 121)
# Mit mehr Elementen dauer es wesentlioh länger:
# camel_capacity = 1000
# camel_pool = (181, 130, 128, 125, 124, 121, 104, 101, 98, 94, 69, 61, 13)
camel_bag = optimal_load(camel_capacity, camel_pool)
camel_load = sum(camel_bag)
print("Beladung:", camel_bag)
print("Summe Beladung:", camel_load)
print("Freie Kapazität:", camel_capacity - camel_load)
Lösung von: Ulrich Berntien ()
/**
* Bestimmt die optimale Beladung.
* @param capacity Die maximale Beladung.
* @param pool Die zur Beladung möglichen Elemente.
* @return Die optimale Beladung, ein Teilmenge von pool.
*/
fun optimalLoad(capacity: Int, pool: IntArray): IntArray {
var tmpOptimalLoad = 0
var tmpOptimalBag = IntArray(0)
for (index in pool.indices)
if (pool[index] <= capacity) {
val bag = optimalLoad(capacity - pool[index], pool.sliceArray(pool.indices - index))
val total = bag.sum() + pool[index]
if (total > tmpOptimalLoad) {
tmpOptimalLoad = total
tmpOptimalBag = bag + pool[index]
}
}
return tmpOptimalBag
}
/**
* Hauptprogramm.
* @param argv Aufrufparamter werden ignotiert.
*/
fun main(argv: Array<String>) {
val capacity = 270
val pool = intArrayOf(18, 32, 34, 45, 57, 63, 69, 94, 98, 121)
// Mit mehr Elementen dauert es wesentlioh länger:
//val capacity = 1000
//val pool = arrayOf(181, 130, 128, 125, 124, 121, 104, 101, 98, 94, 69, 61, 13)
val bag = optimalLoad(capacity, pool)
val load = bag.sum()
println("""
|Beladung: ${bag.contentToString()}
|Summe Beladung: $load
|Freie Kapazität: ${capacity - load}
""".trimMargin())
}
Lösung von: Ulrich Berntien ()
Verifikation/Checksumme:
Kapazität 270 und Gewichte: 69, 63, 45, 34, 32, 18, 5 -> Summe = 266
Für Maximalgewicht 1000 kg mit den Gewichten "{181, 130, 128, 125, 124, 121, 104, 101, 98, 94, 69, 61, 13}" erhält man genau die 1000 kg, wenn man folgende Auswahl trifft: "125, 101, 181, 128, 124, 104, 94, 69, 13, 61"
Achtung:Ab ca. 14 Gewichten beginnt die Aufgabe die Berechenbarkeit zu "knacken"! Die Standardlösung des sogenannten "Rucksack-Problems" weist eine bessere Laufzeit aus, der Lösungsweg ist hingegen nicht sofort einleuchtend.
Aktionen
Neue Lösung hinzufügen
Bewertung
Durchschnittliche Bewertung:
Meta
Zeit: | 4-8 |
Schwierigkeit: | k.A. |
Webcode: | 6gdd-r4zm |
Autor: | Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch) |