0

場所と数量は辞書で管理されているため、場所で利用可能な数量を見つけるロジックを作成しました。

d={'loc2': 500.0, 'loc3': 200.0, 'loc1': 1000.0, 'loc4': 100.0, 'loc5': 50.0}

from operator import itemgetter
def find_combination(locs,qty):
    locs = sorted(locs.items(),key=itemgetter(1),reverse=True)
    result = []
    for loc,val in locs:
        if qty <= 0:
            break
        elif qty - val >= 0:
            qty -= val
            result.append((loc,val))
    return result

数量が口述の最大数量を下回ると、これらの予期しない結果が得られます。

print find_combination(d,1000)
[('loc1', 1000.0)]
print find_combination(d,750)
[('loc2', 500.0), ('loc3', 200.0), ('loc5', 50.0)]
print find_combination(d,1900)
[('loc1', 1000.0), ('loc2', 500.0), ('loc3', 200.0), ('loc4', 100.0), ('loc5', 50.0)] 
print find_combination(d,150)
[('loc4', 100.0), ('loc5', 50.0)]
print find_combination(d,34)
[] # unexpected  # should be [('loc5', 50.0)]
print find_combination(d,88)
[('loc5', 50.0)] # should be [('loc4', 100.0)]
4

3 に答える 3

2

アルゴリズムが必要なものであるかどうかは正確にはわかりません。アイデアが別の場所から特定の量を取得することである場合、アルゴリズムは最適な組み合わせを見つけるのではなく、ちょうど良い組み合わせを見つけます。

あなたの問題は、動的計画法を使用して疑似多項式時間で解くことができる0-1 ナップザック問題と見なすことができます

于 2013-06-18T15:04:19.800 に答える
1

dictionray キーを 1 回だけ使用して、すべての可能な組み合わせを格納する辞書を作成できます。

d={'loc2': 500.0, 'loc3': 200.0, 'loc1': 1000.0, 'loc4': 100.0, 'loc5': 50.0}
from itertools import combinations
comb = {}
for i in range(1,len(d)):
    [comb.__setitem__(sum(j),k) for k,j in zip(combinations(d.keys()  ,i),
                                               combinations(d.values(),i))]

comb辞書は次のようになります。

{50.0: ('loc5',),
 100.0: ('loc4',),
 150.0: ('loc4', 'loc5'),
 200.0: ('loc3',),
 250.0: ('loc3', 'loc5'),
 300.0: ('loc3', 'loc4'),
 350.0: ('loc3', 'loc4', 'loc5'),
 500.0: ('loc2',),
 550.0: ('loc2', 'loc5'),
 600.0: ('loc2', 'loc4'),
 650.0: ('loc2', 'loc4', 'loc5'),
 700.0: ('loc2', 'loc3'),
 750.0: ('loc2', 'loc3', 'loc5'),
 800.0: ('loc2', 'loc3', 'loc4'),
 850.0: ('loc2', 'loc3', 'loc4', 'loc5'),
 1000.0: ('loc1',),
 1050.0: ('loc1', 'loc5'),
 1100.0: ('loc1', 'loc4'),
 1150.0: ('loc1', 'loc4', 'loc5'),
 1200.0: ('loc3', 'loc1'),
 1250.0: ('loc3', 'loc1', 'loc5'),
 1300.0: ('loc3', 'loc1', 'loc4'),
 1350.0: ('loc3', 'loc1', 'loc4', 'loc5'),
 1500.0: ('loc2', 'loc1'),
 1550.0: ('loc2', 'loc1', 'loc5'),
 1600.0: ('loc2', 'loc1', 'loc4'),
 1650.0: ('loc2', 'loc1', 'loc4', 'loc5'),
 1700.0: ('loc2', 'loc3', 'loc1'),
 1750.0: ('loc2', 'loc3', 'loc1', 'loc5'),
 1800.0: ('loc2', 'loc3', 'loc1', 'loc4')}

次に、特定の組み合わせが存在するかどうかを確認する関数を作成できます。

 find_combination = lambda num: comb.get(num, 'NOT A VALID COMBINATION')

例:

 find_combination(1750)
 #('loc2', 'loc3', 'loc1', 'loc5')

 find_combination(1):
 #'NOT A VALID COMBINATION'

編集:辞書が大きくなりすぎる場合は、イテレータに基づいてこの関数を使用することをお勧めします:

def find_combination(d, num):
    from itertools import combinations,izip
    t = ((sum(j),k) for i in range(1,len(d)) \
                    for j,k in izip(combinations(d.values(),i),
                                    combinations(d.keys()  ,i)))
    for comb,k in t:
        if comb==num: return k
于 2013-06-18T14:52:54.433 に答える