Какой алгоритм я могу использовать для равномерного распределения взвешенных объектов на n частей?

Question

Я хочу распределить x(i) объекты (x E {1...n}), где каждый объект имеет вес w(i), на n порции.

Распределение должно быть сделано таким образом, чтобы для всех порций сумма весов была максимально возможной.

Ура! Pratik

Answer 1

Рассчитайте общую сумму весов, разделите на n количество порций, чтобы получить требуемый вес порций. Затем используйте алгоритм упаковки бинов , чтобы попытаться заполнить n баков этого максимального размера.

Обратите внимание, что для правильной работы все веса должны быть меньше веса порции. В противном случае вы нигде не сможете разместить предметы с большим весом.

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

Возможно, вы могли бы сделать немного лучше, если бы использовали очередь с приоритетами.