2

次のような場所と数量の辞書があります

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

今、私が注文するとき、シナリオは以下のようになるはずです.

  • とから製品を150 quantity 取得する必要があるためloc5loc4
  • とから製品を210 quantity 取得する必要があるためloc3loc5
  • andとand1777 quantity から製品を取得する必要があるためloc1loc2loc3loc4
  • とから製品を530 quantity 取得する必要があるためです。loc2loc5

このような状態をどのように達成するのかわかりません。誰かがそれを整理できますか??

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

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 に答える
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 に答える