2

我有一本包含位置和数量的字典，比如

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

现在，当我下订单时，场景应该如下所示，

  • 因为150 quantity 它应该从loc5和loc4
  • 因为210 quantity 它应该从loc3和loc5
  • 因为1777 quantity 它应该从loc1andloc2和loc3and中获取产品loc4
  • 因为530 quantity 它应该从loc2和获取产品loc5。

我不知道如何达到这种条件，有人可以解决吗？

4

4 回答 4

7

将数量放入列表中，排序。用于bisect查找合适的数量。计算较低的数量是否可以完成，如果不能，则选择下一个较高的数量。减去所选数量。如果仍大于 0，则返回该bisect步骤。

编辑：

import bisect

qtys = [50, 100, 200, 500, 1000]

def sack(amt, qtys=qtys):
  res = set()
  while amt > 0:
    pivot = bisect.bisect(qtys, amt)
    if sum(qtys[:pivot]) >= amt:
      amt -= qtys[pivot - 1]
      res.add(pivot - 1)
    else:
      if sum(qtys[:pivot + 1]) < amt:
        raise ValueError('Not enough items to fill the sack')
      res.add(pivot)
      amt -= qtys[pivot]
  return res

print sack(150)
print sack(210)
print sack(1777)
print sack(530)
于 2013-06-04T14:46:59.960 回答
1 
def find_combination(d,val): 
    """(dict,int)->list
    Given a dict with values as numbers, returns the combination of keys whose values sums up to "val"
    In case no values form a perfect sum, picks up the next best case
    """
    new_list = sorted(d.items(),key=lambda y: y[1],reverse=True)
    result = []
    while val > 0:
        min_item = ''
        for item in new_list: 
            if item[0] in result: 
                continue
            new_diff = abs(val - item[1])
            if not min_item or new_diff <= min_diff:
                min_item = item[0]
                min_diff = new_diff
                min_val = item[1]
        result.append(min_item)
        val = val - min_val
    return result

给定

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

这给

>>> combi.find_combination(d,150)
['loc4', 'loc5']
>>> combi.find_combination(d,210)
['loc3', 'loc5']
>>> combi.find_combination(d,1777)
['loc1', 'loc2', 'loc3', 'loc4']
>>> combi.find_combination(d,530)
['loc2', 'loc5']
>>> combi.find_combination(d,160)
['loc3']

必须指出它（非常）低效

于 2013-06-04T16:25:59.297 回答
0

该算法可能对您有所帮助！

def greedy(amount, denoms):
    result = []
    while (amount > 0):
        print amount, denoms, result
        if (amount >= denoms[0]):
            num = amount // denoms[0]
            amount -= (num * denoms[0])
            result.append([denoms[0], num])
        denoms = denoms[1:]
    return result

print greedy(100, [25,10,5,1])
print ""
print greedy(100, [10,5,1])
print ""
print greedy(100, [5,1])
print ""
print greedy(100, [1])
print ""
print greedy(47, [25,10,5,1])

输出将是

100 [25, 10, 5, 1] []
[[25, 4]]

100 [10, 5, 1] []
[[10, 10]]

100 [5, 1] []
[[5, 20]]

100 [1] []
[[1, 100]]

47 [25, 10, 5, 1] []
22 [10, 5, 1] [[25, 1]]
2 [5, 1] [[25, 1], [10, 2]]
2 [1] [[25, 1], [10, 2]]
[[25, 1], [10, 2], [1, 2]]
于 2013-06-04T15:04:33.460 回答
0

即使我认为 Ignacio 和 Atul 的答案更好，如果您想坚持使用字典，您可以使用 while 循环减去数量，

#qnt,the quantity you have

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

dic2= {'loc1':0,'loc2':0,'loc3':0,'loc4':0,'loc5':0} 
while qnt>0:
        if qnt>=dic['loc1']:
             qnt-= dic['loc1']
             dic2['loc1']+=1
        elif qnt>=dic['loc2']:
             qnt-= dic['loc2']
             dic2['loc2']+=1
        elif qnt>=dic['loc3']:
             qnt-= dic['loc3']
             dic2['loc3']+=1
        elif qnt>=dic['loc4']:
             qnt-= dic['loc4']
             dic2['loc4']+=1
        elif qnt>0:
             qnt-= dic['loc5']
             dic2['loc5']+=1

        else:break
print dic2
于 2013-06-04T15:32:51.437 回答