using System;

using System.Linq;

​

public class Item

{

    public int Weight { get; set; }

    public int Value { get; set; }

}

​

​

public class Program

{

    //https://brilliant.org/wiki/backpack-problem/

    //https://stackoverflow.com/questions/50393489/knapsack-c-sharp-implementation-task

    public static void Main()

    {

        int[] value = { 60, 100, 120 };

        int[] weight = { 10, 20, 30 };

        int capacity = 50;

        int itemsCount = 3;

​

        int result = KnapSack(capacity, weight, value, itemsCount);

        Console.WriteLine(result);

        var items = new[]

        {

            new Item {Value = 60, Weight = 10},

            new Item {Value = 100, Weight = 20},

            new Item {Value = 120, Weight = 30},

        };

​

        Console.WriteLine(KnapSack(items, 50));

        Console.WriteLine(KnapSackRecursive(items, 50));

    }

    public static int KnapSack(Item[] items, int capacity)

    {

        int[,] matrix = new int[items.Length + 1, capacity + 1];

        for (int itemIndex = 0; itemIndex <= items.Length; itemIndex++)

        {

            // This adjusts the itemIndex to be 1 based instead of 0 based

            // and in this case 0 is the initial state before an item is

            // considered for the knapsack.

            var currentItem = itemIndex == 0 ? null : items[itemIndex - 1];

            for (int currentCapacity = 0; currentCapacity <= capacity; currentCapacity++)

            {

                // Set the first row and column of the matrix to all zeros

                // This is the state before any items are added and when the

                // potential capacity is zero the value would also be zero.

                if (currentItem == null || currentCapacity == 0)

                {

                    matrix[itemIndex, currentCapacity] = 0;

                }

                // If the current items weight is less than the current capacity

                // then we should see if adding this item to the knapsack 

                // results in a greater value than what was determined for

                // the previous item at this potential capacity.

                else if (currentItem.Weight <= currentCapacity)

                {

                    matrix[itemIndex, currentCapacity] = Math.Max(

                        currentItem.Value 

                            + matrix[itemIndex - 1, currentCapacity - currentItem.Weight],

                        matrix[itemIndex - 1, currentCapacity]);

                }

                // current item will not fit so just set the value to the 

                // what it was after handling the previous item.

                else

                {

                    matrix[itemIndex, currentCapacity] = 

                        matrix[itemIndex - 1, currentCapacity];

                }

            }

        }

​

        // The solution should be the value determined after considering all

        // items at all the intermediate potential capacities.

        return matrix[items.Length, capacity];

    }

    public static int KnapSackRecursive(Item[] items, int capacity)

    {

        // If there are no items or capacity is 0 then return 0

        if (items.Length == 0 || capacity == 0) return 0;

​

        // If there is one item and it fits then return it's value

        // otherwise return 0

        if (items.Length == 1)

        {

            return items[0].Weight < capacity ? items[0].Value : 0;

        }

​

        // keep track of the best value seen.

        int best = 0;

        for (int i = 0; i < items.Length; i++)

        {

            // This is an array of the other items.

            var otherItems = items.Take(i).Concat(items.Skip(i + 1)).ToArray();

​

            // Calculate the best value without using the current item.

            int without = KnapSackRecursive(otherItems, capacity);

            int with = 0;

​

            // If the current item fits then calculate the best value for

            // a capacity less it's weight and with it removed from contention

            // and add the current items value to that.

            if (items[i].Weight <= capacity)

            {

                with = KnapSackRecursive(otherItems, capacity - items[i].Weight) 

                    + items[i].Value;

            }

​

            // The current best is the max of the with or without.

            int currentBest = Math.Max(without, with);

​

            // determine if the current best is the overall best.

            if (currentBest > best)

                best = currentBest;

        }

​

        return best;

    }

    public static int KnapSack(int capacity, int[] weight, int[] value, int itemsCount)

    {

        int[,] K = new int[itemsCount + 1, capacity + 1];

​

        for (int i = 0; i <= itemsCount; ++i)

        {

            for (int w = 0; w <= capacity; ++w)

            {

                if (i == 0 || w == 0)

                    K[i, w] = 0;

                else if (weight[i - 1] <= w)

                    K[i, w] = Math.Max(value[i - 1] + K[i - 1, w - weight[i - 1]], K[i - 1, w]);

                else

                    K[i, w] = K[i - 1, w];

            }

        }

​

        return K[itemsCount, capacity];

    }

}