namespace kolos5_dynamiczny
{
    //w[i,j] - optymalne wzięcie z i pierwszych przedmiotów gdy uniose j kilogramów - kilogramy liczby naturalne
    //w[0,j] - 0 bo jak mam 0 przedmiotów i - ilosc przedmiotow
    //w[i,0] - 0 bo jak uniose 0kg to wartosc 0
    //w[i,j]>=w[i-1,j]
    //w[i,j] >= w[i, j-1]
    //w[i,j] >= w[i-1, j - waga[i]] + cena[i]
    class Program
    {
        static int Plecak(int[]wagi, int[]ceny, int n, int k) // n - ilosc przedmiotow, k - pojemnosc/udzwig
        {
            int[,] wynik = new int[n + 1, k + 1];
            for (int i = 0; i < n+1; i++)
            {
                wynik[i, 0]= 0;
            }
            for (int j = 0; j < k + 1; j++)
            {
                wynik[0, j] = 0;
            }
            for (int i = 1; i < n+1; i++)
            {
                for (int j = 1; j < k+1; j++)
                {
                    int m = Math.Max(wynik[i - 1, j], wynik[i, j - 1]);
                    if (j>=wagi[i-1])
                    {
                        m = Math.Max(m, wynik[i - 1, j - wagi[i - 1]] + ceny[i - 1]);
                    }
                    wynik[i , j ] = m;
                }
            }

            return wynik[n, k];

        }
        static void Main(string[] args)
        {
            int[] wagi = { 16,15,10,5,7 };
            int n = 5;
            int pojemnosc = 50;
            int[] ceny = { 8, 7, 6, 9, 3 };
            Console.WriteLine(Plecak(wagi, ceny, n, pojemnosc));
            Console.ReadKey();
        }
    }
}