various knapsack implementations

Knapsack.cs

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

namespace ConsoleApplication1
{
    public class Program
    {
        public static void Main()
        {
            var knapsackItems = new ZeroOneEagerKnapsack(400)
            {
                new Item { Name = "Map", Weight = 9, Value = 150 },
                new Item { Name = "Water", Weight = 153, Value = 200 },
                new Item { Name = "Compass", Weight = 13, Value = 35 },
                new Item { Name = "Sandwitch", Weight = 50, Value = 160 },
                new Item { Name = "Glucose", Weight = 15, Value = 60 },
                new Item { Name = "Tin", Weight = 68, Value = 45 },
                new Item { Name = "Banana", Weight = 27, Value = 60 },
                new Item { Name = "Apple", Weight = 39, Value = 40 },
                new Item { Name = "Cheese", Weight = 23, Value = 30 },
                new Item { Name = "Beer", Weight = 52, Value = 10 },
                new Item { Name = "Suntan Cream", Weight = 11, Value = 70 },
                new Item { Name = "Camera", Weight = 32, Value = 30 },
                new Item { Name = "T-shirt", Weight = 24, Value = 15 },
                new Item { Name = "Trousers", Weight = 48, Value = 10 },
                new Item { Name = "Umbrella", Weight = 73, Value = 40 },
                new Item { Name = "WaterProof Trousers", Weight = 42, Value = 70 },
                new Item { Name = "Note-Case", Weight = 22, Value = 80 },
                new Item { Name = "Sunglasses", Weight = 7, Value = 20 },
                new Item { Name = "Towel", Weight = 18, Value = 12 },
                new Item { Name = "Socks", Weight = 4, Value = 50 },
                new Item { Name = "Book", Weight = 30, Value = 10 },
                new Item { Name = "waterproof overclothes ", Weight = 43, Value = 75 }
            };
            int value = 0, weight = 0;
            foreach (var item in knapsackItems)
            {
                value += item.Value;
                weight += item.Weight;
                Console.WriteLine(item.Name);
            }
            Console.WriteLine("{0} {1}", value, weight);
        }
    }

    public class Item
    {
        public string Name { get; set; }
        public int Weight { get; set; }
        public int Value { get; set; }
    }

    public class ZeroOneKnapsack : IEnumerable<Item>
    {
        private readonly List<Item> _items;
        private readonly int _weight;
        private int _gcd;

        public ZeroOneKnapsack(int weight)
        {
            _items = new List<Item>();
            _gcd = _weight = weight;
        }

        static int Gcd(int a, int b)
        {
            return b == 0 ? a : Gcd(b, a % b);
        }

        public void Add(Item item)
        {
            _items.Add(item);
            _gcd = Gcd(_gcd, item.Weight);
        }

        //iterative solution
        private IEnumerable<Item> Solve()
        {
            var factoredFullWeight = _weight / _gcd;
            var values = new int[_items.Count + 1, factoredFullWeight + 1];
            var result = new List<Item>();

            for (int i = 1; i <= _items.Count; i++)
            {
                var item = _items[i - 1];
                var factoredWeight = item.Weight / _gcd;
                for (int w = 0; w <= _weight; w++)
                {
                    if (w < factoredWeight)
                    {
                        values[i, w] = values[i - 1, w];
                    }
                    else
                    {
                        values[i, w] = Math.Max(values[i - 1, w], values[i - 1, w - factoredWeight] + item.Value);
                    }
                }
            }

            for (int i = _items.Count, w = factoredFullWeight; i > 0 && w >= 0; i--)
            {
                int value = values[i, w];
                int valuewithout = values[i - 1, w];
                if (value == valuewithout) continue;

                var item = _items[i - 1];
                result.Add(item);
                w -= item.Weight / _gcd;
            }
            result.Reverse();
            return result;
        }

        //recursive solution
        private IEnumerable<Item> SolveR()
        {
            int value;
            return SolveRecursive(_weight, out value, 0, new BitArray(_items.Count), 0);
        }

        private IEnumerable<Item> SolveRecursive(int weight, out int value, int index, BitArray include, int invalue)
        {
            if (index == _items.Count)
            {
                value = invalue;
                return _items.Where((_, i) => include[i]);
            }
            var item = _items[index];
            if (weight <= item.Weight)
            {
                return SolveRecursive(weight, out value, index + 1, include, invalue);
            }
            var with = new BitArray(include) { [index] = true };
            var resultwith = SolveRecursive(weight - item.Weight, out value, index + 1, with, invalue + item.Value);

            int valuewithout;
            var resultwithout = SolveRecursive(weight, out valuewithout, index + 1, include, invalue);

            if (value > valuewithout) return resultwith;

            value = valuewithout;
            return resultwithout;
        }

        public IEnumerator<Item> GetEnumerator() => Solve().GetEnumerator();
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }

    public class ZeroOneEagerKnapsack : IEnumerable<Item>
    {
        private struct BestForWeight
        {
            public ImmutableHashSet<int> Items { get; }
            public int Value { get; }

            public BestForWeight(ImmutableHashSet<int> items, int value)
            {
                Items = items;
                Value = value;
            }
        }

        private readonly List<Item> _items;
        private readonly BestForWeight[] _best;
        private static readonly ImmutableHashSet<int> Empty = ImmutableHashSet<int>.Empty;

        public ZeroOneEagerKnapsack(int weight)
        {
            _items = new List<Item>();
            _best = new BestForWeight[weight + 1];
        }

        public void Add(Item item)
        {
            var index = _items.Count;
            _items.Add(item);
            var capacity = _best.Length - item.Weight;
            if (capacity < 0) return;

            var newbests = new List<BestForWeight>(capacity);
            for (var w = item.Weight; w <= _best.Length; w++)
            {
                var with = _best[w - item.Weight];
                var without = _best[w];
                var value = with.Value + item.Value;
                if (without.Value >= value)
                {
                    newbests.Add(without);
                    continue;
                }
                newbests.Add(new BestForWeight((with.Items ?? Empty).Add(index), value));
            }
            newbests.CopyTo(_best, item.Weight);
        }

        private IEnumerable<Item> Solve()
        {
            return _best[_best.Length - 1].Items.Select(i => _items[i]);
        }

        public IEnumerator<Item> GetEnumerator() => Solve().GetEnumerator();
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }
}