Beste Kombination zur Auffüllung einer Liste

[Valle]

Coool, danke!

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:

#!/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()

@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.

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