Apenas uma ideia: trocar aleatoriamente itens em compartimentos, algo assim:
using System;
using System.Linq;
using System.Collections.Generic;
namespace BinsGenetic
{
class Program
{
private const int NumberOfBins = 10;
private const int NumberOfPoints = 100000;
private const int MinimalPoint = 1;
private const int MaximalPoint = 1000;
private const int NumberOfSwaps = 10000;
static void Main()
{
// Generate empty bins.
var bins = new List<Bin>();
for (int i = 0; i < NumberOfBins; i++)
{
bins.Add(new Bin(i + 1));
}
// Generate 100 points with weight from 1 to 10.
var points = new List<int>();
var rnd = new Random();
for (int i = 0; i < NumberOfPoints; i++)
{
points.Add(rnd.Next(MinimalPoint, MaximalPoint));
}
// Insert points into bins by random order.
int c = 0;
foreach (var point in points.OrderBy(p => p))
{
bins[c].Add(point);
c++;
if (c % NumberOfBins == 0) c = 0;
}
Console.WriteLine("Initial:");
Test(bins);
// Get max and min bin.
for (int i = 0; i < NumberOfSwaps; i++)
{
var b1 = bins[rnd.Next(0, NumberOfBins)];
var b2 = bins[rnd.Next(0, NumberOfBins)];
var p1 = b1.Points[rnd.Next(0, b1.Points.Count)];
var p2 = b2.Points[rnd.Next(0, b2.Points.Count)];
var initialSumBin1 = b1.Points.Sum(p => p);
var initialSumBin2 = b2.Points.Sum(p => p);
var initialDiff = Math.Abs(initialSumBin1 - initialSumBin2);
b1.Add(p2);
b2.Remove(p2);
b2.Add(p1);
b1.Remove(p1);
var finalSumBin1 = b1.Points.Sum(p => p);
var finalSumBin2 = b2.Points.Sum(p => p);
var finalDiff = Math.Abs(finalSumBin1 - finalSumBin2);
if (finalDiff < initialDiff)
{
Console.WriteLine("Optimized {0}:", i);
Test(bins);
}
else
{
b1.Add(p1);
b2.Remove(p1);
b2.Add(p2);
b1.Remove(p2);
}
}
Console.WriteLine("Final:");
Test(bins);
Console.ReadKey();
}
private static void Test(List<Bin> bins)
{
// Test.
for (int i = 0; i < bins.Count; i++)
{
Console.Write("Bin {0}, Count: {1}, Sum:{2}, Points:", i + 1, bins[i].Points.Count, bins[i].Points.Sum(p => p));
//foreach (var point in bins[i].Points.OrderByDescending(p => p))
//{
// Console.Write("{0} ", point);
//}
Console.WriteLine();
}
Console.WriteLine();
}
}
class Bin
{
public readonly List<int> Points;
public int Id { get; private set; }
public Bin(int id)
{
Points = new List<int>();
Id = id;
}
public void Add(int point)
{
Points.Add(point);
}
public void Remove(int point)
{
Points.Remove(point);
}
}
}
Mas eu não tenho idéia de como definir o NumberOfSwaps const. Neste exemplo, eu o testei ... É claro que você não pode ter certeza de que obteve o resultado ideal.
Mas, para algoritmos mais avançados / acadêmicos / prontos para produção, você pode começar sua pesquisa aqui: Problema de empacotamento