数字のリストがあります。私も一定の金額を持っています。合計は、リストのいくつかの数字から作成されます (合計がいくつの数字から作成されているかはわかりません)。可能な数値のリストを取得するための高速なアルゴリズムはありますか? Python で書かれていれば素晴らしいのですが、疑似コードでも良いのです。(Python :P 以外はまだ読めません)
例
list = [1,2,3,10]
sum = 12
result = [2,10]
注：サイズnのリストから別の数値に合計する数値を見つけるアルゴリズムを知っています（ただし、C＃を読むことができず、それが自分のニーズに合っているかどうかを確認できません。Linuxを使用していて、使用してみましたモノですが、エラーが発生し、C＃の操作方法が
わかりません:(そして、すべての組み合わせの数値のリストを合計するアルゴリズムを知っています（ただし、かなり非効率的です。すべての組み合わせは必要ありません.)
この問題は、正確な合計を持つセットを見つけようとしている0-1ナップサック問題に還元されます。解決策は制約に依存します。一般的な場合、この問題はNP完全です。
ただし、最大検索合計（これを呼びましょうS）が高すぎない場合は、動的計画法を使用して問題を解決できます。再帰関数とメモ化を使用して説明します。これは、ボトムアップアプローチよりも理解しやすいものです。
合計が正確にになるf(v, i, S)サブセットの数を返すように、関数をコーディングしてみましょう。これを再帰的に解決するには、最初にベースを分析する必要があります（つまり、空です）。v[i:]Sv[i:]
S == 0：の唯一のサブセット[]は合計0であるため、有効なサブセットです。このため、関数は1を返す必要があります。
S！= 0：の唯一のサブセット[]は合計0であるため、有効なサブセットはありません。このため、関数は0を返す必要があります。
次に、再帰的なケースを分析しましょう（つまり、v[i:]空ではありません）。v[i]現在のサブセットに番号を含めるか、含めないかの2つの選択肢があります。を含めるv[i]と、sumを持つサブセットを探しS - v[i]ます。そうでない場合は、sumを持つサブセットを探しSます。この関数fは、次の方法で実装できます。
def f(v, i, S):
if i >= len(v): return 1 if S == 0 else 0
count = f(v, i + 1, S)
count += f(v, i + 1, S - v[i])
return count
v = [1, 2, 3, 10]
sum = 12
print(f(v, 0, sum))
をチェックするf(v, 0, S) > 0ことで、問題の解決策があるかどうかを知ることができます。ただし、このコードは遅すぎるため、再帰呼び出しごとに2つの新しい呼び出しが生成され、O（2 ^ n）アルゴリズムが生成されます。これで、メモ化を適用して時間O（n * S）で実行できるようになりました。これは、S大きすぎない場合は高速です。
def f(v, i, S, memo):
if i >= len(v): return 1 if S == 0 else 0
if (i, S) not in memo: # <-- Check if value has not been calculated.
count = f(v, i + 1, S, memo)
count += f(v, i + 1, S - v[i], memo)
memo[(i, S)] = count # <-- Memoize calculated result.
return memo[(i, S)] # <-- Return memoized value.
v = [1, 2, 3, 10]
sum = 12
memo = dict()
print(f(v, 0, sum, memo))
gこれで、合計が1つのサブセットを返す関数をコーディングできますS。これを行うには、要素を含むソリューションが少なくとも1つある場合にのみ、要素を追加するだけで十分です。
def f(v, i, S, memo):
# ... same as before ...
def g(v, S, memo):
subset = []
for i, x in enumerate(v):
# Check if there is still a solution if we include v[i]
if f(v, i + 1, S - x, memo) > 0:
subset.append(x)
S -= x
return subset
v = [1, 2, 3, 10]
sum = 12
memo = dict()
if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")
else: print(g(v, sum, memo))
免責事項：このソリューションは、合計が10の[10、10]のサブセットが2つあることを示しています。これは、最初の10が次の10とは異なると想定しているためです。アルゴリズムは、両方の10が等しい（したがって1に答える）と仮定するように修正できますが、それはもう少し複雑です。
あなたがこれを尋ねてから10年後に答えを出していることは知っていますが、これを行う方法を本当に知る必要があり、jbernadasのやり方は私には難しすぎたので、1時間グーグルで調べたところ、pythonが見つかりましたitertools仕事を終わらせるライブラリ！
これが将来の初心者プログラマーに役立つことを願っています。ライブラリをインポートして.combinations()メソッドを使用するだけです。それはとても簡単で、セット内のすべてのサブセットを順番に返します。つまり、次のようになります。
セット[1, 2, 3, 4]と長さ 3 のサブセットの[1, 2, 3][1, 3, 2][2, 3, 1]場合は返されず、[1, 2, 3] のみが返されます。
セットのすべてのサブセットが必要な場合は、反復できます。
import itertools
sequence = [1, 2, 3, 4]
for i in range(len(sequence)):
for j in itertools.combinations(sequence, i):
print(j)
出力は次のようになります。
() (1,) (2,) (3,) (4,) (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) (1 , 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)
この助けを願っています！
したがって、ロジックは数値を逆ソートし、数値のリストがlで、形成される合計がsであるとします。
for i in b:
if(a(round(n-i,2),b[b.index(i)+1:])):
r.append(i)
return True
return False
次に、このループを通過し、番号がlから順番に選択され、それがiであるとします。iが合計の一部であるかどうかの 2 つのケースが考えられます。したがって、 iが解の一部であると仮定すると、問題はlでl[l.index(i+1):]あり、sがsiであると見なされます。したがって、関数が a(l,s) の場合、 を呼び出しますa(l[l.index(i+1):] ,s-i)。iがs の一部でない場合は、リストからsを作成する必要がありl[l.index(i+1):]ます。したがって、どちらの場合も似ています。変化するのは、i が s の一部である場合は s=si であり、そうでない場合は s=s のみです。
ここで問題を軽減するために、l の数値が s より大きい場合、l が空になるまでそれらを削除して複雑さを軽減します。その場合、選択された数値はソリューションの一部ではなく、false を返します。
if(len(b)==0):
return False
while(b[0]>n):
b.remove(b[0])
if(len(b)==0):
return False
l の要素が 1 つしか残っていない場合、それが s の一部である場合は true を返すか、そうでない場合は false を返し、ループは他の番号を通過します。
if(b[0]==n):
r.append(b[0])
return True
if(len(b)==1):
return False
b..を使用した場合はループに注意してください.しかし、bは私たちのリストのみです.そして、Pythonでの浮動小数点計算が原因で間違った答えが得られないように、可能な限り四捨五入しました.
r=[]
list_of_numbers=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
list_of_numbers=sorted(list_of_numbers)
list_of_numbers.reverse()
sum_to_be_formed=401.54
def a(n,b):
global r
if(len(b)==0):
return False
while(b[0]>n):
b.remove(b[0])
if(len(b)==0):
return False
if(b[0]==n):
r.append(b[0])
return True
if(len(b)==1):
return False
for i in b:
if(a(round(n-i,2),b[b.index(i)+1:])):
r.append(i)
return True
return False
if(a(sum_to_be_formed,list_of_numbers)):
print(r)
このソリューションは、上で説明したソリューションよりも高速に動作します。ただし、これは正の数に対してのみ機能します。ただし、解決策がある場合はうまく機能します。そうでない場合は、ループから抜け出すのに時間がかかります。
実行例は次のようになります
l=[1,6,7,8,10]
and s=22 i.e. s=1+6+7+8
so it goes through like this
1.) [10, 8, 7, 6, 1] 22
i.e. 10 is selected to be part of 22..so s=22-10=12 and l=l.remove(10)
2.) [8, 7, 6, 1] 12
i.e. 8 is selected to be part of 12..so s=12-8=4 and l=l.remove(8)
3.) [7, 6, 1] 4
now 7,6 are removed and 1!=4 so it will return false for this execution where 8 is selected.
4.)[6, 1] 5
i.e. 7 is selected to be part of 12..so s=12-7=5 and l=l.remove(7)
now 6 are removed and 1!=5 so it will return false for this execution where 7 is selected.
5.)[1] 6
i.e. 6 is selected to be part of 12..so s=12-6=6 and l=l.remove(6)
now 1!=6 so it will return false for this execution where 6 is selected.
6.)[] 11
i.e. 1 is selected to be part of 12..so s=12-1=1 and l=l.remove(1)
now l is empty so all the cases for which 10 was a part of s are false and so 10 is not a part of s and we now start with 8 and same cases follow.
7.)[7, 6, 1] 14
8.)[6, 1] 7
9.)[1] 1
あまり良くない自分のコンピューターで実行した比較を行うためだけに。使用して
l=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,145.21,123.56,11.90,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
と
s=2000
私のループは 1018 回、31 ミリ秒実行されました。
前のコード ループは 3415587 回実行され、16 秒近くかかりました。
ただし、解決策が存在しない場合、私のコードは数分以上実行されたので停止しました。以前のコードは約 17 ミリ秒しか実行されず、以前のコードは負の数でも機能します。
だから私はいくつかの改善ができると思います。