n個の部分に均等に重み付けされたオブジェクトを配布するために使用できるアルゴリズムはどれですか？

Question

私はオブジェクト(x E {1...n})を配達したいと思っています。それぞれのオブジェクトはw(i)の体重で、nになります。

分布は、すべての部分について重みの合計ができるだけ等しいような方法で行う必要があります。

乾杯！ Pratik

Answer 1

必要な部分の重量を得るために、重みの合計をnで割った数を計算します。次に、bin packing algorithmを使用して、この最大サイズのnビンを入力してください。

これが正しく動作するためには、すべての重量が部分重量より小さくなければならないことに注意してください。さもなければ、大きな体重のアイテムをどこにでも置くことはできません。

Answer 2

あなたはMultiprocessor schedulingの問題について説明していると思います。ここで

はジュリアの実装です：

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

あなたはプライオリティキューを使用した場合は、おそらく少し良く行うことができます。