Ich möchte x(i) Objekte (x E {1...n}) verteilen, wobei jedes Objekt Gewicht w(i) hat, in n Portionen.Welchen Algorithmus kann ich verwenden, um gewichtete Objekte gleichmäßig in n Teilen zu verteilen?
Die Verteilung sollte so erfolgen, dass für alle Teile die Summe der Gewichte möglichst gleich ist.
Prost! Pratik
Berechnen Sie die Gesamtsumme der Gewichte, dividieren Sie durch n, die Anzahl der Portionen, um das erforderliche Portionsgewicht zu erhalten. Verwenden Sie dann eine bin packing algorithm, um n Bins dieser maximalen Größe zu füllen.
Beachten Sie, dass alle Gewichte weniger als das Portionsgewicht sein müssen, damit dies richtig funktioniert. Andernfalls können Sie keine Gegenstände mit großem Gewicht überall platzieren.
ein wenig Preprocessing wird sich um den Eckfall kümmern - das erforderliche Portionsgewicht finden, alle Gewichte entfernen, die größer sind als der Portion und sie in eigene Behälter legen, dann den bin Packing-Algorithmus für die verbleibenden nk-Gewichte und nk ausführen Mülleimer. –
Ich denke, Sie beschreiben das Multiprocessor scheduling Problem.
Hier ist eine Julia Umsetzung:
"""
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
Man könnte wahrscheinlich ein wenig besser, wenn Sie eine Prioritätswarteschlange verwendet.
Versuchen Sie, den maximalen Unterschied zwischen zwei Teilen, den durchschnittlichen Unterschied zwischen den Teilen oder etwas anderes zu minimieren? –