Belirtilen numaraya kadar değer ekleyen bir listenin indekslerini alın

Question

Değerlerim var ve ben bir sayı giriyorum. İşlev, değeri sayıya kadar olan listeden indisleri döndürmelidir. Sorun, listede çift numaralar ve geri dönen indeksler aynı olmamalıdır. İşte sahip olduğum şey ama çözüm temiz görünmüyor. Daha iyi bir yolu var mı?

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) 

Çıktı

[6, 5, 3] 

Sonra İstemediğim budur [6, 6, 3] alacağı eklemeden önce listeyi kontrol etmedi edin.

Answer 1

Değerler listesi sıralanırsa, aşağıdaki kod istediğiniz şeyi yapar. Buradaki hile, listeyi ters sırada yürütmek.

Ancak, buradaki düzenlemeyi ve son testi not edin!

Düzenleme: sorun alt kümesi toplamı sorunu olarak bilinen (Wikipedia bakınız) ve NP-tamamlanır. Onu hemen tanımalıydım, benim kötü. Bu temel olarak basit & verimli bir çözüm olmadığı anlamına gelir. En basit çözüm, tüm olası kombinasyonları denemek olacaktır, ancak değerler listeniz büyükse, tamamlanması çok uzun sürecektir.

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