Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

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

Bitte melde dich an um einen Kommentar abzugeben

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

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 4-8
Schwierigkeit: k.A.
Webcode: 6gdd-r4zm
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen