我可以为分配有权重的物品到n个部分中使用哪种算法？

Question

我想分配 x(i) 个对象 (x E {1...n})，每个对象的重量为 w(i)，分配到 n 个部分中。

分配应该这样做：对于所有部分，它们的重量总和尽可能相等。

干杯！ Pratik

- Pratik Garg

---

你是想要最小化任意两个部分之间的最大差异，平均差异还是其他什么？ - Martin Hock

Answer 1

计算所有重量的总和，然后除以n，即份数，得到所需的每份重量。然后使用装箱问题算法尝试填充n个最大尺寸的箱子。

请注意，为使此方法有效，所有物品的重量都必须小于每份重量。否则，您无法在任何地方放置大重量物品。

- pjp

---

一些预处理可以解决角落情况 - 找到所需部分的重量，删除任何大于该部分的重量并将它们放入自己的箱子中，然后对剩余的n-k个重量和n-k个箱子运行装箱算法。 - Martin DeMello

Answer 2

我认为你在描述多处理器调度问题。

这里是一个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

如果您使用优先队列，可能会更好。

- Mageek