IA-ENI/Metaheuristics/MetaheuristicsPCL/KnapsackProblem/KnapsackProblem.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace MetaheuristicsPCL
{
    public class KnapsackProblem : IProblem
    {
        protected List<Box> boxes = null;
        public double MaxWeight { get; set; }

        public static Random randomGenerator = null;

        public const int NB_NEIGHBOURS = 30;

        public KnapsackProblem()
        {
            boxes = new List<Box>();

            boxes.Add(new Box("A", 4, 15));
            boxes.Add(new Box("B", 7, 15));
            boxes.Add(new Box("C", 10, 20));
            boxes.Add(new Box("D", 3, 10));
            boxes.Add(new Box("E", 6, 11));
            boxes.Add(new Box("F", 12, 16));
            boxes.Add(new Box("G", 11, 12));
            boxes.Add(new Box("H", 16, 22));
            boxes.Add(new Box("I", 5, 12));
            boxes.Add(new Box("J", 14, 21));
            boxes.Add(new Box("K", 4, 10));
            boxes.Add(new Box("L", 3, 7));

            MaxWeight = 20;
            if (randomGenerator == null)
            {
                randomGenerator = new Random();
            }
        }

        public KnapsackProblem(int _nbBoxes, double _maxWeight, double _maxValue)
        {
            boxes = new List<Box>();
            MaxWeight = _maxWeight;
            if (randomGenerator == null)
            {
                randomGenerator = new Random();
            }

            for (int i = 0; i < _nbBoxes; i++)
            {
                boxes.Add(new Box(i.ToString(), randomGenerator.NextDouble() * _maxWeight, randomGenerator.NextDouble() * _maxValue));
            }
        }

        public List<Box> Boxes() {
            return boxes;
        }

        public List<ISolution> Neighbourhood(ISolution _currentSolution)
        {
            List<ISolution> neighbours = new List<ISolution>();
            List<Box> possibleBoxes = boxes;

            for (int i = 0; i < NB_NEIGHBOURS; i++)
            {
                KnapsackSolution newSol = new KnapsackSolution((KnapsackSolution)_currentSolution);
                int index = randomGenerator.Next(0, newSol.LoadedContent.Count);
                newSol.LoadedContent.RemoveAt(index);

                double enableSpace = MaxWeight - newSol.Weight;
                List<Box> availableBoxes = possibleBoxes.Except(newSol.LoadedContent).Where(x => (x.Weight <= enableSpace)).ToList();

                while (enableSpace > 0 && availableBoxes.Count != 0)
                {
                    index = randomGenerator.Next(0, availableBoxes.Count);
                    newSol.LoadedContent.Add(availableBoxes.ElementAt(index));
                    enableSpace = MaxWeight - newSol.Weight;
                    availableBoxes = possibleBoxes.Except(newSol.LoadedContent).Where(x => (x.Weight <= enableSpace)).ToList();
                }

                neighbours.Add(newSol);
            }
            return neighbours;
        }

        public ISolution RandomSolution()
        {
            KnapsackSolution solution = new KnapsackSolution();
            List<Box> possibleBoxes = boxes;

            double enableSpace = MaxWeight;
            List<Box> availableBoxes = possibleBoxes.Where(x => (x.Weight <= enableSpace)).ToList();

            while (enableSpace > 0 && availableBoxes.Count != 0)
            {
                int index = randomGenerator.Next(0, availableBoxes.Count);
                solution.LoadedContent.Add(availableBoxes.ElementAt(index));
                enableSpace = MaxWeight - solution.Weight;
                availableBoxes = possibleBoxes.Except(solution.LoadedContent).Where(x => (x.Weight <= enableSpace)).ToList();
            }

            return solution;
        }

        public ISolution BestSolution(List<ISolution> _listSolutions)
        {
            return _listSolutions.Where(x => x.Value.Equals(_listSolutions.Max(y => y.Value))).FirstOrDefault();
        }
    }
}