Преобразовать рекурсию в динамическую
у меня есть задача: массив цифр [8 1 2 8 2 10 4 5], нужно определить, могут ли какие-либо его элементы составлять половину его общей суммы. В примере сумма элементов равна 40, полусумма равна 20. Элементов может быть 8,2,10 или 5,1,4,10. Неважно, какие цифры, только истинный или ложный результат. Я проверяю все возможные суммы цифр рекурсией, и я запутался, как преобразовать это в циклы
private static boolean isExist(int[] data, int n, int sum) {
if (sum == 0)
return true;
if (n <= 0)
return false;
if (data[n - 1] == sum)
return true;
if (sum < data[n - 1])
return isExist(data, n - 1, sum);
return isExist(data, n - 1, sum - data[n - 1]) || isExist(data, n - 1, sum);
}
Нет, это верное утверждение. Это работает . Мне нужно переписать его на цикл вместо рекурсии. Я просто описал, что делает этот код
Ответы 1
Составьте массив A[] длины sum+1, сделайте A[0]=1
Для каждого элемента значения e: проверьте в обратном направлении (от конца массива к началу) if A[i-e]==1, в этом случае сделайте A[i]=1. (Это означает, что сумма i может быть составлена с использованием текущего элемента и ранее проверенных)
Если A[sum] становится равным 1, то необходимое подмножество существует.
Рабочий пример на Python для демонстрации:
L = [7, 9, 3, 4, 6, 7]
S = sum(L) // 2
A = [0]*(S+1)
A[0] = 1
for e in L:
for i in range(S, e-1, -1): // scan backward
if A[i-e]:
A[i] = 1
print(A, A[-1] > 0)
>> [1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] True
L = [7, 9, 3, 4, 6, 13]
>> [1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] False
извините, но я не понимаю. Например, [1 5 7 1 ], сумма = 7, сделать массив A[8], A[0] = 1, затем для 1 элемента -> A[8] -> 8 - 1 = 7 и 7!=1 , что сохранять в A[8]-????
Для этого случая (размер массива 8) последним элементом является A[7], а A[7-7]==0, поэтому A[7]=1, и существует сумма
У меня плохой пример, извините. Для 7 9 3 4 6 7 - сумма 18 мы берем 7 -> A[18] = 11 , а затем проверяем A[11] для 6 элементов?
Я добавил код Python
почему мы используем A[sum+1],? какой шаг между 7 и 6 элементами в этом массиве?
Потому что последним элементом такого массива является A[sum], а нам нужно A[0], так как «допустимо пустое множество»
then wee check A[11] for 6 element? Нет, проверяем, что сумма 11 уже составлена из других элементов. Это условие не срабатывает для первых 7, но срабатывает для последних 7
Мне очень трудно это понять. попробую разобраться. Спасибо за вашу помощь.
Попробуйте реализовать шаги. После значения 7 заполняется только ячейка массива 7. После 7 и 9 - 7, 9 и 16. После 7, 9,3 - 3,7,9,10,12, 19 и т.д.
Я думаю, в постановке задачи упоминалась бы сумма подмножеств. Тогда ваше утверждение «Элементы могут быть 8,2,10 или 5,1,4,10» будет иметь смысл. Если это так, вы должны найти все подмножества этого массива, а затем найти сумму. Сумма BTW никогда не будет меньше элемента.