CODEWITHSUNDEEP
pythonalgorithm
DY92
DY92

Reputation: 437

Algorithm: to distribute n elements into m buckets, such that the maximum sum of elements among buckets is minimum

The goal is to minimize(max(bucket1,bucket2,...,bucketn))

I have decided, that greedy approach must work:

def algo(values,k = 4):
  values_sort = sorted(values,reverse = True)#sorting values in descending order
  buckets = [[] for b in range(k)]#creating buckets

  for i in range(len(values_sort)):#If buckets are empty add biggest elements to them
    if i < k:
      buckets[i].append(values_sort[i])

    else:# Greedy approach
      sums = [sum(b) for b in buckets]
      index = sums.index(min(sums))#add new element to the local minimum(the smallest sum of time among all buckets)
      buckets[index].append(values_sort[i])

  return buckets

I have compared my greedy solution to the random assingment:

#random assingment to the buckets
def algo_random(time,k):
  buckets = [[] for k in range(k)]
  count = 0
  for i in range(len(time)):
    buckets[count].append(time[i])
    count +=1
    if count == k:
      count = 0

  return buckets

I ran the code bellow, where I compared greedy solution to the random assingment 1 million times:

for i in range(1000000):
  time = [uniform(0, 1000.0) for i in range(100)]
  #algo random
  rand = algo_random(time,4)
  t_rand = max([sum(x) for x in rand]) 

  #algo optimal
  algo_o = algo(time,4)
  t_o = max([sum(x) for x in algo_o])

  if t_rand < t_o:
    print('False')

And in 2 cases out of 1 million, random assingement was better than greedy solution. It means, that my algorithm(greedy solution) is not optimal. Can you help me to correct my algorithm?

EDIT: I have noticed, that algorithm works well for big number of records and bad for small number of records

Upvotes: 1

Views: 911

Answers (1)

templatetypedef
templatetypedef

Reputation: 372982

This problem is sometimes called the job shop scheduling problem and is known to be NP-hard, so there are no known greedy algorithms that run efficiently and always produce the optimal solution.

Upvotes: 2

Related Questions