从lis获取数据

Question

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

{'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，它应该取loc1和loc2和loc3和loc4的乘积
• 对于530 quantity，它应该取loc2和loc5的乘积。你知道吗

我不知道如何达到这样的条件，有人能解决吗？？你知道吗

Answer 1

这个算法可能会帮助你！你知道吗

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]]

Answer 2

把数量排成一个单子，分类。Use ^{} to find an appropriate quantity.计算较低的数量是否可以满足，如果不能满足，则选择下一个较高的数量。减去所选数量。如果仍然大于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)

Answer 3

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']

必须指出它（极其）低效