Fetching data from the list

Question

I have a dictionary with location and quantity, like

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

Now when i'll make a order the scenario should be like below,

• for 150 quantity it should take product from loc5 and loc4
• for 210 quantity it should take product from loc3 and loc5
• for 1777 quantity it should take product from loc1 and loc2 and loc3 and loc4
• for 530 quantity it should take product from loc2 and loc5.

I don't know how achieve such kind of condition, can anyone sort it out??

Answer 1

Put the quantities in a list, sorted. Use bisect to find an appropriate quantity. Calculate if the lower quantities can fulfill, and if not pick the next higher quantity. Subtract the selected quantity. If still greater than 0, go back to the bisect step.

EDIT:

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 2

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

Given

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

This gives

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

Must point out that it is (horribly) inefficient

Answer 3

Even though i think Ignacio and Atul answers are better if you wanna stick with the dictionary you can use a while loop that subtracts the quantity,

#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

Answer 4

This algorithm might help you!

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

And the out put will be

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