OptimalSelectionOfItems

import java.util.Scanner;
import java.util.Arrays;

public class scratch_1
{
    public static boolean statzero = false;
    public static int iteracii = 0;

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);

        System.out.println("въведи вместимост на раницата в кг : ");
        int M = Integer.parseInt(scan.nextLine());
        System.out.println("въведи броя на предметите (между 2 и 5) : ");
        int N = scan.nextInt();
        int[] G = new int[N];

        for (int i = 0; i < G.length; i++) {
            System.out.println("въведи теглото (не по-малко от 2 кг) на предмет [" + i + "] : ");
            G[i] = scan.nextInt();
        }
        System.out.println();

        SortarrayG(G);
        checkbackpack(M, G);

    }

    private static void SortarrayG(int[] arr) {

        int n = arr.length;
        for (int i = 1; i < n; ++i)
        {
            int eXtracted = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > eXtracted) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = eXtracted;
        }
    }

    private static void checkbackpack(int M, int[] G) {
        Scanner stop = new Scanner(System.in);
        int[] STAT = new int[G.length];
        int index = 0;
        int startiterindex = 0;
        boolean eop = false;

        while (M > 0 && !eop) {

            if (G[index] <= M) {
                M = M - G[index];
                STAT[index] = STAT[index] + 1;
                statzero = false;

                System.out.println();
                System.out.println(" итерация номер :" + ++iteracii + " ----------  ");
                System.out.println("индекса на текущия предмет е : " + index);
                System.out.println("а теглото (g) на предмета е : " + G[index]);
                System.out.println("в раницата (" + (M + G[index]) + " - " + G[index] + ") остават свободни " + M + " кг");
                System.out.println("stat масив [бр]: " + Arrays.toString(STAT));
                System.out.println("G-масив  [кг]: " + Arrays.toString(G));


            } else {
                System.out.println();
                System.out.println(" итерация номер :" + ++iteracii + "   ");
                System.out.println("индекса на текущия предмет е : " + index);
                System.out.println("а теглото (g) на предмета е : " + G[index]);
                System.out.println("текущия предмет " + G[index] + "кг е по-тежък от свободното в раницата " + M + " кг");
                System.out.println("stat масив [бр]: " + Arrays.toString(STAT));
                System.out.println("G-масив  [кг]: " + Arrays.toString(G));

                System.out.println();
                if (index + 1 < G.length) {
                    System.out.println("преминаваме към слезващия предмет ------->");
                    System.out.println("ЗА ПРОДЪЛЖАВАНЕ НАТИСНИ) : n ");
                    String Pause = stop.next("n");
                    index++;
                    System.out.println("в раницата са свободни " + M + " кг");


                } else {
                    System.out.println(" края на масива с килограмите на предметите ");
                    System.out.println();
                    System.out.println("индекса на последния предмет е : " + index);
                    System.out.println("а теглото (g) на предмета е : " + G[index]);
                    System.out.println("в раницата все аще остават свободни " + M + " кг");
                    System.out.println("stat масив [бр]: " + Arrays.toString(STAT));
                    System.out.println("G-масив  [кг]: " + Arrays.toString(G));
                    System.out.println("(за продължение натисни) : n ");

                    String Pause = stop.next("n");
                    System.out.println(" започват обратни итерации  ");

                    if (M > 0 || index == G.length + 1) {

                        for (int j = index; j >= 0; j--) {
                            if (STAT[j] > 0) {

                                System.out.println();
                                System.out.println("изваждаме по 1 предмет в обратен ред");

                                System.out.println("(за продължение натисни) : y ");
                                Pause = stop.next("n");
                                STAT[j] = STAT[j] - 1;
                                M = M + G[j];

                                if (j == G.length - 1 && STAT[j] > 0) {
                                    eop = true;
                                }
                                System.out.println("stat масив [бр]: " + Arrays.toString(STAT));
                                System.out.println("G-масив  [кг]: " + Arrays.toString(G));
                                System.out.println("изваден 1 предмет от " + G[j] + " кг");
                                System.out.println("в раницата свободните килограми станаха : " + M);

                                System.out.println("(за продължение натисни) : y ");
                                Pause = stop.next("n");

                                if (startiterindex + j + 1 < G.length) {
                                    startiterindex = j + 1;

                                    index = startiterindex;
                                } else {
                                    index = G.length - 1;
                                }

                            }
                        }
                    }
                }
            }
        }
        if (M == 0) {

            System.out.println();
            System.out.println("--------------------");
            System.out.println("  задачата има решение");
            System.out.println("--------------------");
            System.out.println(" в раницата остават  свободни " + M + " кг");
            System.out.println("stat масив [бр]: " + Arrays.toString(STAT));
            System.out.println("G-масив [кг]: " + Arrays.toString(G));
        }
    }
}