Алгоритм: распределить n элементов в m сегментов так, чтобы максимальная сумма элементов между сегментами была минимальной.

Question

Цель: minimize(max(bucket1,bucket2,...,bucketn))

Я решил, что жадный подход должен работать:

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

Я сравнил свое жадное решение со случайным заданием:

#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

Я запустил приведенный ниже код, где я 1 миллион раз сравнивал жадное решение со случайным назначением:

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

И в 2 случаях из 1 миллиона случайное определение было лучше, чем жадное решение. Значит, мой алгоритм (жадное решение) не оптимален. Можете ли вы помочь мне исправить мой алгоритм?

EDIT: Я заметил, что этот алгоритм хорошо работает для большого количества записей и плохо работает для небольшого количества записей

Answer 1

Эту проблему иногда называют проблемой планирования цеха работ, и она известна как NP-сложная, поэтому не существует известных жадных алгоритмов, которые работают эффективно и всегда дают оптимальное решение.