値が指定された数値に加算されるリストのインデックスを取得する

Question

私は値のリストを持っていて、数字を入力します。この関数は、値が数値に加算されるリスト内のインデックスを返す必要があります。問題は、リストに重複した数字が含まれていて、返されたインデックスが同じであってはならないことです。ここに私が持っているが、ソリューションはきれいに見えません。より良い方法がありますか？

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) 

出力

[6, 5, 3] 

私はその後、私は私が望むものではありませんどの[6, 6, 3]になるだろう追加する前にリストをチェックdidntの場合。

Answer 1

値の一覧がソートされている場合、次のコードは必要な処理を行います。ここでのトリックは、リストを逆順に移動することです。

ただし、機能の編集と最後のテストに注意してください。

編集：問題はサブセット和問題として知られている（Wikipediaを参照）、NP-完了する。すぐにそれを認識していたはずです、私の悪い。これは、基本的に効率的な解決方法がないことを意味します。&最も簡単な解決策はすべての可能な組み合わせを試すことですが、値のリストが大きい場合は、完了には時間がかかります。

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