Ağırlıklı nesneleri n bölümlerinde eşit olarak dağıtmak için hangi algoritmayı kullanabilirim?

Question

Her nesnenin w(i), n bölümlerine x(i) nesneler (x E {1...n}) nesnelerini dağıtmak istiyorum. Dağılım, bütün bölümler için ağırlık toplamının mümkün olduğu kadar eşit olması gerektiği şekilde yapılmalıdır.

Şerefe! Pratik

Answer 1

İstenen porsiyon ağırlığını elde etmek için ağırlıkların toplamını hesaplayın, n ile bölme sayısını bölümlere ayırın. Daha sonra bu maksimum boyutun n kutularını denemek ve doldurmak için bin packing algorithm kullanın.

Tüm ağırlıkların düzgün çalışması için bunun ağırlığından daha az olması gerektiğini unutmayın. Aksi halde, herhangi bir yerde büyük ağırlığa sahip eşyaları yerleştiremezsiniz.

Answer 2

Bence Multiprocessor scheduling sorununu açıklıyorsunuz.

İşte Julia uygulamasıdır:

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

Bir öncelikli sıraya kullandıysanız muhtemelen biraz daha iyi yapabilirdi.