У меня проблема с моей функцией возврата, она зацикливается на определенных данных. Я не могу написать здесь весь программный код, но могу поставить здесь свою функцию.
bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen)
{
if(moneyA == half)
return true;
else if(index >= quantity)
return false;
moneyA += values[index];
if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
{
ifChosen[index] = true;
return true;
};
moneyA -= values[index];
if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
{
ifChosen[index] = false;
return true;
};
return false;
}
Теперь вот объяснение:
количество - количество элементов в массиве значений
значения - массив чисел
index - переменная для управления рекурсией
moneyA - переменная, в которой хранится сумма элементов из значений массива
half- число, которое moneyA должно достигнуть после выполнения рекурсии
ifChosen - массив логических элементов, ссылающихся на значения массива
Функция получает количество элементов, равное длине массива значений, значения массива с числами в немотсортированный от самого высокого к низшему, индекс управляет рекурсией и по умолчанию равен 0, поэтому он начинается с первого элемента, переменной moneyA, которая хранит числа из массива значений и должна достигать половины, равной половине чисел, суммируемых из массива значений и ifChosenхранит выбранные номера.
WЭто делает дырочная функция, она суммирует элементы из массива значений и проверяет, достигла ли она половины, если она меньше половины, добавляет ее к moneyA и помечает в ifChosen, затем переходит к следующему, если сумма больше половины, которую она получаетвернуться и снять отметку в массиве ifChosen и вычесть из moneyA.Он всегда должен получать самые высокие элементы.
Вот простой пример:
6 - number of elements
50, 20, 19, 15, 2, 2 - elements stored in values array
total sum is - 108
half of elements - 54
Результат для этого должен быть:
50, 2, 2 - marked as true in ifChosen
20, 19, 15 - marked as false in ifChosen
Конечно, для этогоПростой пример, он делает большую работу, но для более сложных, которые имеют больше чисел, и одно число встречается более одного раза, оно повторяется и рекурсия никогда не останавливается.Я фактически работал над этим в течение 1,5 недель и спросил всех своих друзей, но никто не знает, что с ним не так.Я знаю, что это имеет какое-то отношение к проблеме с рюкзаком, но у меня ее еще не было, и я все еще должен учиться.
Я с нетерпением жду любого ответа, который мог бы помочь.
Извините за пунктуацию, но я здесь впервые и не привык к форматированию.
Вот один пример:
89 86 83 67 53 45 5 1
44 43 34 33 33 24 23 23 23 22 21 21 19 12 11 9 8 7 5 3 2 2 2 1 1 1 1 1
real 0m28.007s
user 0m27.926s
sys 0m0.028s
Теперь, по-моему, одна петля навсегда: 43 элемента:
12 2 2 1 3 4 5 6 7 89 33 12 45 23 44 23 11 44 1 3 5 7 88 33 8 19 43 22 86 5 34 23 21 67 83 24 21 53 9 11 34 1 1
@ Карл Билефельдт Да, я знаю, что существует так много комбинаций, поэтому я пытаюсь ускорить их.Пока это все, что я получил, но это дает мне неверные результаты для определенного ввода.Кто-нибудь может сделать это правильно, он работает намного быстрее, чем раньше?
bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen){
if(index>=quantity && moneyA == half){ return true;}
else if(index>=quantity) return false;
moneyA+=values[index];
ifChosen[index]=true;
if(moneyA<=half){
shareMoney(quantity,values,index+1,moneyA, half,ifChosen);
if(moneyA==half) return true;
return true;
}else{
shareMoney(quantity,values,index+1,moneyA, half,ifChosen);
moneyA-=values[index];
ifChosen[index]=false;
return true;
}
return false;}