Problema di ordinamento del contenitore: si prega di aiutare a categorizzare

Solo un'idea: scambia gli elementi in modo casuale in contenitori, qualcosa del genere:

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);
        }
    }
}

Ma non ho idea di come impostare NumberOfSwaps const. In questo esempio l'ho impostato testando ... Ovviamente non puoi essere sicuro di aver ottenuto il risultato ottimale.

Ma per gli algoritmi più avanzati / accademici / pronti per la produzione puoi iniziare la tua ricerca qui: Problema di imballaggio del contenitore

Questo problema può essere risolto esattamente in tempo polinomiale usando la programmazione dinamica. Lascia che E [ i, b ] sia il più piccolo errore possibile sui contenitori b , b + 1 , .. ., k quando quei raccoglitori contengono elementi i , i +1, ..., n e nessun altro . Osserva che vogliamo calcolare E [1,1], che faremo tabulando tutti i valori E [ i, b ] per 1 & Leq; i & Leq; n e 1 & leq; b & Leq; k .

Ho intenzione di scrivere c [ b ] per la capacità del b 'bin, w [ i ] per il peso dell'elemento i e w [ i, j ] per w [ i ] + ... + w [ j ].

Per prima cosa, osserva che, per ogni i , E [ i, k ] = | w [ i, n ] - c [ k ] |, perché questo è l'unico errore possibile nel mettere tutti gli elementi i attraverso n in bin k . Per calcolare E [ i, b ] per alcuni b < k , osserva che inseriamo gli elementi i , ..., j (per alcuni j & geq; i ) in bin b e voci j +1, ..., n in contenitori b +1, .. ., k ; oppure mettiamo tutti gli elementi i , ..., n in contenitori b +1, ..., k . Pertanto,

E [ i, b ] = min ({ E [ i, b +1]} ∪ {| w [ i, j ] - c [ b ] | + E [ j +1, b +1]: i < j & leq; n }

Poiché ogni E [ i, b ] dipende solo dai valori E [ i ', b' ] per i '> io e b '> b , possiamo solo calcolarli in ordine decrescente di b e i . Quindi, possiamo calcolare E [1,1] nel tempo qualcosa come O (n ² k) . Poiché l'input contiene i costi n e k , l'input ha una lunghezza almeno nk , quindi questo è un vero algoritmo tempo polinomiale (come distinto dagli algoritmi pseudopolinomiali che di solito si ottengono per problemi di imballaggio del contenitore).