Как говорится в названии, нам задан набор чисел, и нам нужно найти все подмножества с суммой, равной к определенному числу (мы назовем его M).Backtracking - заданный набор чисел, найти все подмножества с суммой, равной M (M задано)
Большинство из вас, вероятно, уже знакомы с проблемой, поэтому давайте перейдем к погоне. Я только недавно получил программу обратного отслеживания (я должен сказать вам, что до сих пор я полный бюст), поэтому я пытаюсь решить более «классические» проблемы.
Теперь, ниже, вы увидите мой код, который пытается решить эту проблему, в обратном порядке. Тем не менее, код дает
Исключение в потоке «основного» java.lang.StackOverflowError
на линии 44 (я подсвеченным), а также, я не знаю, если это на самом деле решает проблему в обратном пути или если мой код является просто полным и полным кормом.
package project3;
import java.util.*;
public class Main {
static int[] A = { 1, 2, 3, 4 }; // the array in which we are given the numbers.->
static int n = A.length; // -> I have it filled with 1, 2, 3, 4 for testing purposes
static int m = 5; // the number which the subsets' sum must be
static int[] Sol = new int[50]; // the array in which solutions are stored up->
//->until they are syso'ed, after that it gets zero'ed
static void makeZero() { // make the solution array 0 again
for (int i = 0; i < 50; i++)
Sol[i] = 0;
}
static void show() { // outputs the solution array
int i = 0;
while (Sol[i] != 0 && i < 49) {
System.out.print(Sol[i] + " ");
i++;
}
}
public static void main(String[] args) {
Sol[0]=A[0]; back(0, 1, A[0], 1);// we start with the first number in the array as->
} // -> both the first element as the solution and part of the sum
static int back(int i, int j, int S, int nr) {
if (i < n && j < n) {
if (A[j] + S == m) {// if we got a solution, we output it and then go to the ->
Sol[nr] = A[j]; // -> next element if possible, if not, we start again with ->
show(); // -> the following element
if (j < n - 1)
back(i, j++, S, nr);
else if (i < n - 1) {
makeZero();
back(i + 1, i + 2, 0, 0);
}
}
else if (A[j] + S > m) { // condition for stoping and starting over with another element
if (j < n - 1) // we try again with the following element
back(i, j++, S, nr);// LINE 44 : Exception in thread "main" java.lang.StackOverflowError
else if (i < n - 2 && j == n - 1) { // if not possible, we start again with the following element
makeZero();
back(i + 1, i + 2, 0, 0);
} else if (i == n - 2 && j == n - 1) // if we are down to the last element->
if (A[i + 1] == m) // ->we check if it is ==m
System.out.println(A[i + 1]);
}
else if (j < n - 1 && A[j] + S < m) { // obvious
Sol[nr++] = A[j];
S = S + A[j];
back(i, j + 1, S, nr);
}
else if (j == n - 1 && A[j] + S < m && i < n - 2) {// if the sum!=m and the are no more elements->
makeZero(); // ->start again with another element
back(i + 1, i + 2, 0, 0);
}
else { // if we are down to the last element, we check if it is ==m
if(A[i+1]==n-1)
System.out.println(A[i + 1]);
}
}
return 0;
}
}
ПРИМЕЧАНИЕ: Я надеюсь, что мои комментарии являются полезными, но если они более запутанным, чем помогает просто игнорировать их, я думаю, что вы можете получить представление о том, что я делаю без них.
Тем не менее, я хотел бы узнать, почему коды дают эту ошибку (я знаю, в каком контексте эта ошибка вообще дается, но я не понимаю, почему я ее здесь, поскольку я не могу см. любой бесконечный цикл) и как заставить код работать, а также независимо от того, возвращается ли он обратно.
Это происходит, когда объем памяти в стеке выполнения программы достигает максимальной емкости. Самый простой способ добиться этой ошибки - использовать рекурсию, в которой вы постоянно нажимаете на стек выполнения, вызывая функцию внутри функции снова и снова, не возвращаясь. это то, что вы делаете с последовательными вызовами назад(). –
@RAZ_Muh_Taz Я отредактировал последнюю часть. –
Хорошо, прежде всего я бы использовал очередь, на которую вы нажимаете, а затем удаляете ее, когда вы достигаете своего лимита числа 50, вместо массива размером 50. Также вы даете ему «худший сценарий» из 1, поскольку сумма любого из этих чисел в вашем массиве никогда не будет складываться до 1, что объясняет переполнение стека и многочисленные количества обращений к back() –