Problema de classificação da pasta - Por favor, ajude a categorizar

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

Esse problema pode ser resolvido exatamente em tempo polinomial usando programação dinâmica. Seja E [<> i, b ] o menor erro possível nos escaninhos b , b + 1 , .. ., k quando essas caixas contêm itens i , i +1, ..., n e nenhum outro . Observe que desejamos calcular E [1,1], o que faremos tabulando todos os valores E [ i, b ] para 1 & leq; i & leq; n e 1 & leq; b & k .

Vou escrever c [ b ] para a capacidade do b 'th bin, w [ i ] para o peso do item i 'e w [ i, j ] para w [ i ] + ... + w [ j ].

Primeiro, observe que, para qualquer i , E [ i, k ] = | w [ i, n ] - c [ k ] | porque esse é o único erro possível ao colocar todos os itens i através de n no bin k . Para calcular E [<> i, b ] para alguns b < k , observe que ou colocamos itens i , ..., j (para alguns j & geq; i ) em bin b e itens j +1, ..., n em compartimentos b +1, .. ., k ; ou colocamos todos os itens i , ..., n em compartimentos b +1, ..., k . Portanto,

E [ i, b ] = min ({ E [ i, b +1]} | {| w [ i, j ] - c [ b ] | + E [ j +1, b +1]: i }

Como cada E [<> i, b ] depende apenas dos valores E [ i ', b' ] para i '> i e b '> b , podemos apenas calculá-los em ordem decrescente de b e i . Então, podemos calcular E [1,1] no tempo algo como O (n ² k) . Como a entrada contém os pesos n e k , a entrada tem comprimento pelo menos nk , então este é um verdadeiro algoritmo de tempo polinomial (como distintos dos algoritmos pseudo-polinomiais que você normalmente obtém para problemas de empacotamento).