Programmieren lernen

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 ()

# Eine Lösung finden und ausgeben
memory = {}

def optimale_beladung(vorrat, kapazitaet):
    if len(vorrat) == 0:
        return ()

    identifier = str((kapazitaet, ">= sum") + vorrat)
    if identifier not in memory:    
        ware = vorrat[0]
        restkapazitaet = kapazitaet - ware
    
        if restkapazitaet < 0:
            memory[identifier] = ()
            return memory[identifier]

        vorrat_ohne_ware = vorrat[1:]
        optimum_ohne_ware = optimale_beladung(vorrat_ohne_ware, kapazitaet)
        optimum_mit_ware = (ware,) + optimale_beladung(vorrat_ohne_ware, restkapazitaet)
       
        if sum(optimum_ohne_ware) > sum(optimum_mit_ware):
            memory[identifier] = optimum_ohne_ware
        else:
            memory[identifier] = optimum_mit_ware

    return memory[identifier]

def ausgabe(optimum, vorrat, kapazitaet):
    print('vorrat: {}\nlen(vorrat): {}\nsum(vorrat): {}\nmax-kapazität: {}'.format(vorrat, len(vorrat), sum(vorrat), kapazitaet))
    print("an optimum: {} <= {}".format(sum(optimum), tuple(sorted(list(optimum)))))
    print('-- ')

tests = (
    { 'maximale_kapazitaet': 2,
      'initialer_vorrat': (3, 5, 2)},
    { 'maximale_kapazitaet': 6,
      'initialer_vorrat': (3, 5, 7, 5, 2)},
    { 'maximale_kapazitaet': 270,
      'initialer_vorrat': (5, 57, 98, 32, 121, 34, 45, 63, 69, 18, 94)},
    { 'maximale_kapazitaet': 1000,
      'initialer_vorrat': (81, 130, 128, 125, 124, 121, 104, 101, 98, 94, 69, 61, 13)},
    { 'maximale_kapazitaet': 4567,
      'initialer_vorrat': (109, 11, 301, 19, 19, 17, 123, 121, 101, 101, 31, 911, 671, 611, 131, 217, 371, 391, 519, 37, 43, 51, 61, 397)},
)

map(lambda t: ausgabe(optimale_beladung(tuple(sorted(list(t['initialer_vorrat']))), t['maximale_kapazitaet']), 
                      t['initialer_vorrat'],
                      t['maximale_kapazitaet']),
              tests)
                

Lösung von: Rc Mlz ()

#!/usr/bin/env raku

sub optimale_beladung(@vorrat, @beladung, $kapazität) {
    state %memo;
    return @beladung if @vorrat.elems == 0;
    my Str $identifier = $kapazität ~ ' >= sum ' ~ @vorrat;
    if not %memo{$identifier}:exists {
        return %memo{$identifier} = () if @vorrat.head > $kapazität;
        my $ohne = optimale_beladung(@vorrat.tail(*- 1), @beladung, $kapazität);
        my $mit = optimale_beladung(@vorrat.tail(*- 1), (@vorrat.head, @beladung).flat, $kapazität - @vorrat.head);
        %memo{$identifier} = sum($mit) > sum($ohne) ?? $mit !! $ohne
    }
    %memo{$identifier}
}

sub MAIN(Bool :$test=False, UInt :$kapazität?, :$vorrat?) {
    # usage: raku kamele-beladen.raku --kapazität=270 --vorrat="5 18 32 34 45 57 63 69 94 98 121"
    if not $test {
        my $beladung = optimale_beladung($vorrat.words.sort, (), $kapazität);
        say "-" x 10;
        say "Kapazität:\t" ~ $kapazität;
        say "Vorrat:\t\t" ~ $vorrat;
        say "." x 5;
        say "Summe Beladung:\t" ~ sum $beladung;
        say "Beladung:\t" ~ sort $beladung;
        say "-" x 10;
    } else {
        my @tests =
                { maximale_kapazität => 2,
                  initialer_vorrat   => (3, 5, 2) },
                { maximale_kapazität => 6,
                  initialer_vorrat   => (3, 5, 7, 2) },
                { maximale_kapazität => 270,
                  initialer_vorrat   => (5, 18, 32, 34, 45, 57, 63, 69, 94, 98, 121) },
                { maximale_kapazität => 1000,
                  initialer_vorrat   => (181, 130, 128, 125, 124, 121, 104, 101, 98, 94, 69, 61, 13) },
                { maximale_kapazität => 2657,
                  initialer_vorrat   => (109, 111, 301, 119, 19, 177, 123, 121, 101, 101, 31, 131, 217, 371, 391, 37, 43, 51, 61, 397)}
                ;
        for @tests -> $test {
            my $beladung = optimale_beladung($test<initialer_vorrat>.sort, (), $test<maximale_kapazität>);
            print sum $beladung;
            say " == sum $beladung"
        }
    }
}
                

Lösung von: Rc Mlz ()

# Alle Lösungen finden und ausgeben
memory = {}

def optimale_beladungen(vorrat, kapazitaet):
    if len(vorrat) == 0:
        return ((),)
    
    identifier = str((kapazitaet, ">= sum") + vorrat)
    if identifier not in memory:        
        ware = vorrat[0]
        vorrat_ohne_ware = vorrat[1:]
        
        restkapazitaet = kapazitaet - ware
        if restkapazitaet < 0:
            memory[identifier] = ((),)
            return memory[identifier]    

        optima_ohne_ware = optimale_beladungen(vorrat_ohne_ware, kapazitaet)
        
        optima_fuer_restkapazitaet = optimale_beladungen(vorrat_ohne_ware, restkapazitaet)
        optima_mit_ware = tuple(map(lambda optimum: (ware,) + optimum, optima_fuer_restkapazitaet))
        
        if sum(optima_ohne_ware[0]) > sum(optima_mit_ware[0]):
            memory[identifier] = optima_ohne_ware    
        elif sum(optima_ohne_ware[0]) == sum(optima_mit_ware[0]):
            memory[identifier] = optima_ohne_ware + optima_mit_ware
        else:
            memory[identifier] = optima_mit_ware

    return memory[identifier]


def ausgabe(optima, vorrat, kapazitaet):
    print('vorrat: {}\nlen(vorrat): {}\nsum(vorrat): {}\nmax-kapazität: {}'.format(vorrat, len(vorrat), sum(vorrat), kapazitaet))
    i = 1
    for optimum in optima:
        print("optimum {}: {} <== {}".format(i, sum(optimum), tuple(sorted(list(optimum)))))
        i += 1
    print('--')

tests = (
    { 'maximale_kapazitaet': 2,
      'initialer_vorrat': (3, 5, 2)},
    { 'maximale_kapazitaet': 6,
      'initialer_vorrat': (3, 5, 7, 2)},
    { 'maximale_kapazitaet': 270,
      'initialer_vorrat': (5, 18, 32, 34, 45, 57, 63, 69, 94, 98, 121)},
    { 'maximale_kapazitaet': 1000,
      'initialer_vorrat': (181, 130, 128, 125, 124, 121, 104, 101, 98, 94, 69, 61, 13)},
    { 'maximale_kapazitaet': 2657,
      'initialer_vorrat': (109, 111, 301, 119, 19, 177, 123, 121, 101, 101, 31, 131, 217, 371, 391, 37, 43, 51, 61, 397)},
)

map(lambda t: ausgabe(optimale_beladungen(tuple(sorted(list(t['initialer_vorrat']))), t['maximale_kapazitaet']), 
                      t['initialer_vorrat'],
                      t['maximale_kapazitaet']),
              tests)
                

Lösung von: Rc Mlz ()