Erhalte die Indizes einer Liste, deren Wert sich zu der angegebenen Zahl addiert

Question

Ich habe eine Liste von Werten und ich gebe eine Nummer ein. Die Funktion muss die Indizes in der Liste zurückgeben, deren Wert sich zu der Zahl addiert. Das Problem besteht darin, dass die Liste doppelte Zahlen enthält und die zurückgegebenen Indizes nicht identisch sein sollten. Hier ist, was ich habe, aber die Lösung sieht nicht sauber aus. Gibt es einen besseren Weg?

finalList = [] 
def getIndices(number): 
    values = [10,20,20,50,100,200,200,500,1000,2000,2000,5000] 
    for i in range(len(values)): 
    if values[i] == number: 
     if i not in finalList: 
     finalList.append(i) 
     else: 
     finalList.append(i-1) 
     return values 
    elif values[i] < number: 
     continue 
    else: 
     number = number - values[i-1] 
     if i-1 not in finalList: 
     finalList.append(i-1) 
     else: 
     finalList.append(i-2) 
     if number <= 0: 
     break 
     return getIndices(number) 


result = getIndices(450) 
print(result) 

Ausgabe

[6, 5, 3] 

Wenn ich vor dem Anhängen der Liste überprüfen didnt dann würde ich [6, 6, 3] bekommen, die nicht das, was ich will.

Answer 1

Wenn die Liste der Werte sortiert ist, wird der folgende Code tun, was Sie wollen. Der Trick besteht darin, die Liste in umgekehrter Reihenfolge zu durchlaufen.

Beachten Sie aber die Bearbeitung und den letzten Test in der Funktion!

Edit: Das Problem als Teilmenge Summe Problem bekannt ist (siehe Wikipedia) und NP-vollständig ist. Hätte es sofort erkannt, mein Schlechter. Dies bedeutet im Grunde, dass es keine einfache & effiziente Lösung gibt. Die einfachste Lösung wäre, alle möglichen Kombinationen auszuprobieren, aber wenn Ihre Werteliste groß ist, wird es einfach zu lange dauern.

def getIndices(number, values): 
    '''Return a tuple (n, l) where l is a list of indices in 'values' and the 
    following condition holds: n + sum(values[i] for i in l) == number. 

    values -- sorted list of numbers 
    number -- sum to search for 

    >>> values=[10,20,20,50,100,200,200,500,1000,2000,2000,5000] 
    >>> getIndices(18000, values) 
    (6900, [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]) 
    >>> getIndices(450, values) 
    (0, [6, 5, 3]) 
    >>> getIndices(15, values) 
    (5, [0]) 
    >>> getIndices(10, values) 
    (0, [0]) 
    >>> getIndices(5, values) 
    (5, []) 
    >>> getIndices(0, values) 
    (0, []) 

    This simplicist algorithm does not always find a solution with 'n' == 0, 
    even if one exists. The following test fails, it returns (10, [2]) 
    instead. 

    >>> getIndices(40, [20, 20, 30]) 
    (0, [0, 1]) 

    ''' 
    n = number 
    l = [] 

    for i in range(len(values) - 1, -1, -1): 
     if values[i] <= n: 
      l.append(i) 
      n -= values[i] 

    assert(n + sum(values[i] for i in l) == number) 
    return n, l 


if __name__ == '__main__': 
    import doctest 
    doctest.testmod()