using System;

public class Program

{

    //0-1 kanpsack

    //fractional knapsack

    //Unbounded knapsack

    static int[,] dp;

    public static void Main()

    {

        int bw = 10;

        int [] weight = new int[] {1,2,4,5};

        int [] values = new int[] {5,3,2,7}; //15

        dp = new int[bw+1, 4];

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

            for(int j=0;j<4;j++){

                dp[i,j] = -1;

            }   

        int result = KnapSack(weight, values, 10, 3);

        for(int i=0;i<11;i++){

            for(int j=0;j<4;j++){

                Console.Write("{0} ",dp[i,j]);

            }

            Console.WriteLine();

        }

        Console.WriteLine(result);

    }

    public static int KanpSackTable(int[] weight, int[] values, int bagWeight, int size){

        int[,] dp = new int[bagWeight+1, size+1];

        for(int i=0;i<bagWeight+1;i++){

            for(int j=0;j<size+1;j++){

                if(i == 0 || j ==0){

                    dp[i, j] = 0;

                }

            }

        }

        for(int i=1;i<bagWeight+1;i++){

            for(int j=1;j<size+1;j++){

                if(bagWeight >= dp[bagWeight-weight[i], j-1])

                    dp[i, j] = Math.Max(values[j] + dp[bagWeight-weight[i], j-1],  dp[weight[i], j-1]);

                else

                    dp[i, j] =  dp[weight[i], j-1];

            }

        }

        return dp[bagWeight, size];

    }

​

    public static int KnapSack(int[] weight, int[] values, int bagWeight, int size){

        if(size < 0 || bagWeight <= 0)

            return 0;

        if(dp[bagWeight, size] != -1) return dp[bagWeight, size];

        if(bagWeight >= weight[size])

            dp[bagWeight, size] = Math.Max(values[size] + KnapSack(weight, values, bagWeight-weight[size], size-1)

                                    ,KnapSack(weight, values, bagWeight, size-1));

        else

            dp[bagWeight, size] = KnapSack(weight, values, bagWeight, size-1);

        return dp[bagWeight, size];

    }

}