using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        int[] wt = new int[] { 53, 88, 78, 72, 30, 46 };

        int[] val = new int[] { 45, 98, 3, 76, 9, 48 };

        int W = 81;

        int n = val.Length;

        int[, ] dp = new int[n + 1, W + 1];

        Console.WriteLine(knapSack(W, wt, val, n, dp));

        Console.WriteLine(getSelectedItems(n, W, val, dp));

        Console.WriteLine("Hello World");

    }

    static String getSelectedItems(int n, int W, int[] val, int[, ] dp)

    {

        List<int> selectedItems = new List<int>();

        int tempWeight = W;

        int cost = dp[n, tempWeight];

        for (int i = n; i > 0; i--)

        {

            int j = containsCost(cost, i - 1, W, dp);

            if (j == -1) {

                selectedItems.Add(i);

                cost = cost - val[i - 1];

            }

        }

        selectedItems.Sort();

        return selectedItems.Count > 0 ? String.Join(",", selectedItems) : "-";

    }

    static int containsCost(int n, int i, int W, int[, ] dp) 

    {

        for (int j = 0; j <= W; j++) 

        {

            if (dp[i, j] == n)

            {

                return j;

            }

        }

        return -1;

    }

    // A utility function that returns

    // maximum of two integers

    static int max(int a, int b)

    {

         return (a > b) ? a : b;

    }

    // Returns the maximum value that

    // can be put in a knapsack of

    // capacity W

    static int knapSack(int W, int[] wt,

                        int[] val, int n, int[, ] K)

    {

        int i, w;

        // Build table K[][] in bottom

        // up manner

        for (i = 0; i <= n; i++)

        {

            for (w = 0; w <= W; w++)

            {

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

                    K[i, w] = 0;

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

                    K[i, w] = Math.Max(

                        val[i - 1]

                        + K[i - 1, w - wt[i - 1]],

                        K[i - 1, w]);

                else

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

            }

        }

        return K[n, W];

    }

    /*

    static int knapSackRec(int W, int[] wt, int[] val,

                           int n, int[, ] dp)

    {

        // Base condition

        if (n == 0 || W == 0)

            return 0;

        if (dp[n, W] != -1)

            return dp[n, W];

        if (wt[n - 1] > W)

        {

            return dp[n, W] = knapSackRec(W, wt, val, n - 1, dp);

        }

        else

        {

            int costWithItemIncluded = 

                val[n - 1] + knapSackRec(W - wt[n - 1], wt, val, n - 1, dp);

            int costWithoutItem = knapSackRec(W, wt, val, n - 1, dp);

            if (costWithItemIncluded > costWithoutItem)

            {

                dp[n, W] = costWithItemIncluded;

            }

            else

            {

                dp[n, W] = costWithoutItem;

            }

            return dp[n, W];

        }

    }

    static String knapSack(int W, int[] wt, int[] val, int N)

    { 

        // Declare the table dynamically

        int[, ] dp = new int[N + 1, W + 1];

        // Loop to initially filled the

        // table with -1

        for (int i = 0; i < N + 1; i++)

            for (int j = 0; j < W + 1; j++)

                dp[i, j] = -1;

        int weight = knapSackRec(W, wt, val, N, dp);

        Console.WriteLine(weight);

        List<int> selectedItems = new List<int>();

        int tempWeight = W;

        int cost = dp[N, tempWeight];

        for (int i = N; i > 0; i--)

        {

            int j = containsCost(cost, i - 1, W, dp);

            if (j == -1) {

                Console.WriteLine("i " + i + " val " + cost);

                selectedItems.Add(i);

                cost = cost - val[i - 1];

            }

        }

        selectedItems.Sort();

        return selectedItems.Count > 0 ? String.Join(",", selectedItems) : "-";

    }

    static int containsCost(int n, int i, int W, int[, ] dp) 

    {

        for (int j = 0; j <= W; j++) 

        {

            if (dp[i, j] == n)

            {

                return j;

            }

        }

        return -1;

    }*/

}