AW: Beste Kombination zur Auffüllung einer Liste
Da hast du natürlich recht: es fehlen einige Kombinationen. Ich habe da wohl die Iterationen mit und ohne L3 (weil L3 ja eh nicht geht) vermischt. (L0+L3) wäre dann bei 14a und (L1+L3) bei 23a einzusortieren.
Für einen Algorithmus bietet sich ein rekursiver Ansatz an. Später kann man den ja immer noch serialisieren. Als Datenstruktur für eine Lösung wäre ein array of Integer gut geeignet, in dem die Anzahl der einzelnen Listen vermerkt ist. Ich hab da mal quick and dirty was zusammengeschrieben, das du vielleicht als Basis nehmen kannst. Insbesondere die statischen Arrays wird man wohl durch dynamische ersetzen müssen.
Delphi-Quellcode:
program Project255;
{$APPTYPE CONSOLE} {$R *.res} uses System.SysUtils, System.Math; type TSolution = array[0..3] of Integer; TListe = array[0..2] of Integer; const Soll: TListe = (3,2,4); Listen: array[0..3] of TListe = ((3,2,0), (0,0,2), (0,0,1), (4,0,0)); Kosten: array[0..3] of Integer = (10, 5, 4, 10); function CalcKosten(const Solution: TSolution): Integer; var I: Integer; begin Result := 0; for I := 0 to 3 do Result := Result + Solution[I] * Kosten[I]; end; procedure WriteIteration(const Solution: TSolution; const Liste: TListe; res: Integer); var I: Integer; S: string; begin S := '('; for I := 0 to 3 do S := S + IntToStr(Solution[I]) + ','; S[Length(S)] := ')'; S := S + '['; for I := 0 to 2 do S := S + IntToStr(Liste[I]) + ','; S[Length(S)] := ']'; if res = 0 then begin S := S + ' Lösung: ' + IntToStr(CalcKosten(Solution)); end else if res > 0 then begin S := S + ' überfüllt'; end; Writeln(S); end; procedure Iteration(var Solution: TSolution; const Liste: TListe; Index: Integer); var newListe: TListe; I: Integer; newRes: Integer; res: Integer; begin Inc(Solution[Index]); for I := 0 to 2 do newListe[I] := Liste[I] + Listen[Index, I]; res := 0; for I := 0 to 2 do begin newRes := CompareValue(newListe[I], Soll[I]); if res <> newRes then begin if res = 0 then res := newRes else if newRes > 0 then res := newRes; end; end; WriteIteration(Solution, newListe, res); if res < 0 then begin Iteration(Solution, newListe, Index); end; Dec(Solution[Index]); if Index < 3 then begin Iteration(Solution, Liste, Index + 1); end; end; procedure Main; var Solution: TSolution; Liste: TListe; I: Integer; begin for I := 0 to 3 do Solution[I] := 0; for I := 0 to 2 do Liste[I] := 0; Iteration(Solution, Liste, 0); end; begin try Main; except on E: Exception do Writeln(E.ClassName, ': ', E.Message); end; Readln; end. |
AW: Beste Kombination zur Auffüllung einer Liste
Coool, danke! :thumb:
Mein Ansatz war auch ein rekursiver, er funktioniert auch, hat allerdings viele Lösungen mehrfach gefunden... Hier dein Code nach Anpassungen, Vereinfachungen und "Pythonifizierung":
Code:
@BUG: Also. ^^ Es geht um Buchungen einer Ferienwohnung. Diese Buchung kann mit Aufbettungen ausgestattet werden. Eine Aufbettung entspricht nicht nur einfach einem Bett, sondern einer Art 3er Tupel: (Anzahl Erwachsenenbetten, Anzahl Kinderbetten, Anzahl Babybetten). Für jede Ferienwohnung gibt es eine ganze Menge solcher Aufbettungsmöglichkeiten. Das liegt daran, dass es einzelne oder zB. doppelstöckige Betten gibt (Doppelstockbett = (0, 2, 0)). Außerdem können teilweise auch kleinere Häuser ("Studios") aufgeschlossen werden, die erneut Betten bieten.
#!/usr/bin/env python3
# -*- coding: utf-8 -*- soll = [3, 2, 4] listen = [ [3, 2, 0], [0, 0, 2], [0, 0, 1], [4, 0, 0], ] kosten = [10, 5, 4, 10] def CalcKosten(solution): return sum(s * k for s, k in zip(solution, kosten)) def CompareLists(a, b): """ Gibt 0 zurück, wenn beide Listen gleich sind. Gibt 1 zurück, wenn wenigstens ein Element in a größer ist. Gibt -1 zurück, wenn wenigstens ein Element in a kleiner, aber keins größer ist. """ if all([i == j for i, j in zip(a, b)]): return 0 elif any([i > j for i, j in zip(a, b)]): return 1 return -1 def Iteration(solution, liste, index=0): solution[index] += 1 newListe = [j + k for j, k in zip(liste, listen[index])] res = CompareLists(newListe, soll) if res == 0: print('Lösung: %s, %i' % (solution, CalcKosten(solution))) if res == -1: Iteration(solution, newListe, index) solution[index] -= 1 if index < len(listen)-1: Iteration(solution, liste, index + 1) def main(): solution = [0] * len(listen) liste = [0] * len(soll) Iteration(solution, liste); if __name__ == '__main__': main() Gegeben habe ich also ein Tupel an notwendigen Aufbettungen. Also eine Differenz aus Inklusivbetten und tatsächlichen Teilnehmern der Buchung. Und gesucht ist die billigste Kombination aus Aufbettungsoptionen, die genau die notwendige Bettenzahl abdeckt. Sicher hätte man das Problem auch anders lösen können. Aber das war meine erste Idee. Und die hat mich so sehr fasziniert, dass ich jetzt auch wissen wollte, wie man es allgemein löst. Vielen Dank euch allen. :-) Liebe Grüße, Valentin |
AW: Beste Kombination zur Auffüllung einer Liste
Jetzt wo ich deine Lösung so sehe: Vermutlich könnte man auch was mit dynamische Programmierung erreichen.
Gerade, wenn die Sollwerte klein und die Anzahl der möglichen Kombinationen groß ist, sollte das etwas bringen. Das könnte so aussehen: Für jeden Aufbettungswert kleiner des Soll-Werts wird nur die beste Zusammenstellung aus den Listen gespeichert. In jeder Iteration wird ein Element aus den Restlisten genommen und mit allen möglichen/sinnvollen Faktoren auf die aktuelle Zusammenstellung addiert. Ungültige Zwischenergebnisse werden weggeschmissen und alle optimalen Zwischenergebnisse für die nächste Iteration aufgehoben. Das Interessante an dieser Lösung: Du braucht nur Anzahl der Listen viele Iterationen und die Liste der optimalen Zwischenergebnisse wird für ein Soll-Wert von [n, m, k] höchstens (n+1)*(m+1)*(k+1) groß :) Zitat:
Aber ist vermutlich nicht von dir beeinflussbar :mrgreen: EDIT/OT: Zitat:
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 16:55 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz