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

现在，当数量低于 dict 中的最大数量时，它会给出这些意想不到的结果：

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

您可以只使用一次字典键创建一个存储所有可能组合的字典，这将给出：

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 回答
0

这是一个意想不到的结果？

当qty = 34和val = 50,qty - val >= 0将评估为假。

类似于qty = 88和val = 100

你的程序的结果对我来说听起来不错:)

附带说明：

def find_combination(locs,qty):
  locs = sorted(d.items(),key=itemgetter(1),reverse=True)

但我猜你的意思是locs = sorted(locs.items(), ...

于 2013-06-18T15:06:15.053 回答