Jakiego algorytmu użyć do równomiernego rozłożenia ważonych obiektów w n porcjach?

Question

Chcę rozpowszechniać x(i) obiektów (x E {1...n}), gdzie każdy obiekt ma wagę w(i), do części n.

Rozkład należy wykonać w taki sposób, aby dla wszystkich porcji suma wag była jak najbardziej równa.

Pozdrawiam! Pratik

Answer 1

Obliczyć całkowitą sumę wag, podzielić przez n, liczbę porcji, aby uzyskać wymaganą wagę porcji. Następnie użyj numeru bin packing algorithm, aby wypróbować i wypełnić n tego maksymalnego rozmiaru.

Należy pamiętać, że wszystkie ciężary muszą być mniejsze niż waga porcji, aby to działało prawidłowo. W przeciwnym razie nie będzie można umieszczać przedmiotów o dużej wadze w dowolnym miejscu.

Answer 2

Myślę, że opisujesz problem z Multiprocessor scheduling.

Oto realizacja Julia:

""" 
Solves the Multiprocessor Scheduling problem using the Longest Processing Time algorithm 

    PROBLEM: (NP-hard) 
     Given: 
      - set of jobs, each with a length 
      - a number of processors 
     Find: 
      - divide the jobs among the processors such that none overlap 
       which minimizes the total processing time 

    ALGORITHM: 
     - sort the jobs by processing time 
     - assign them to the machine with the earliest end time so far 
     Achieves an upper bound of 4/3 - 1/(3m) of optimal 

    RETURNS: 
     assignments, ith index → machine for the ith job 
""" 
function multiprocessor_scheduling_longest_processing_time{R<:Real}(
    jobs::AbstractVector{R}, 
    m::Integer, # number of processors 
    ) 

    durations = zeros(R, m) 
    assignments = Array(Int, length(jobs)) 

    for i in sortperm(jobs, rev=true) # p[1] is the index of the longest job in `jobs` 
     best_index = indmin(durations) 
     durations[best_index] += jobs[i] 
     assignments[i] = best_index 
    end 

    assignments 
end 

Prawdopodobnie mógłby zrobić trochę lepiej, jeśli stosowany kolejkę priorytetową.