public class Ruc
{
    public static void main(String[] args)
    {
        int[] weights = new int[] {6, 3, 4, 2, 5};
        int[] priсes = new int[]{5, 1, 3, 3, 6};
        int sum = 15;

        int k = weights.length;

        int[][] A = new int[k + 1][sum +1 ];

        //рюкзак
        for (int n = 0; n <= sum; ++n)
            A[0][n] = 0;
        for (int s = 1; s <= k; ++s){
            for (int n = 0; n <= sum; ++n){
                A[s][n] = A[s-1][n];
                if (n >= weights[s-1] && (A[s-1][n-weights[s-1]] + priсes[s-1] > A[s][n]))
                    A[s][n] = A[s-1][n-weights[s-1]] + priсes[s-1];
            }
        }

        for (int s = 0; s <= k; ++s){                            //тестовый вывод
            for (int n = 0; n <= sum; ++n){
                System.out.print(A[s][n] + " ");
            }
            System.out.println();
        }

        print(k, sum, A, weights);                               //вызов метода
    }


    static void print(int s, int n, int[][] A, int[] w)           //вывод результата на экран
    {
        if (A[s][n] == 0)
            return;
        else
            if (A[s-1][n] == A[s][n]){
                print(s - 1, n, A, w);

            }
        else{
                print(s - 1, n - w[s-1], A, w);
                System.out.print(A[s][n]+ " ");
                System.out.print(w[s-1] + " ");
                System.out.println(s);
            }
    }

}

static List<Integer> inArray(int s, int n, int[][] A, int[] w, List<Integer> list)
    {
        List<Integer> copy = list;
        if (A[s][n] == 0)
            return list;
        else
        if (A[s-1][n] == A[s][n]){
            list = inArray(s - 1, n, A, w, copy);

        }
        else{
            list = inArray(s - 1, n - w[s-1], A, w, copy);
            list.add(s);
        }
        return list;
    }