[ Поиск ] - [ Пользователи ] - [ Календарь ]
Полная Версия: Не удается придумать алгоритм
Страницы: 1, 2
Владимир55
Имеется 500 чисел и нужно выбрать из них любое количество чисел, что бы сумма выбранных была точно ровна 21345,24.

Каждое число можно взять только один раз. Числа с десятичной точкой типа 3241,25.

Ничего путного не придумав, решил выбирать числа случайным образом. Поскольку задача разовая, то надеялся угадать.

Однако, не вышло! Даже перебрав скриптом сто тысяч вариантов, нужного не нашел!

По какому алгоритму можно корректно решить эту задачу?

(Искомая комбинация в общем списке точно имеется).
Valick
Владимир55, попробуйте вычитатать из 21345,24 числа в рандомном порядке, как только будет равно нулю, то всё, если меньше нуля, то возващаетесь на шаг назад и сканируете все чсла подряд на предмет нужного, если такого нет, то возвращаетесь на два шага назад выбираете рандомное число и затем опять сканируете все числа подряд. Это примерный алгоритм, но за основу можно взять.


_____________
Стимулятор ~yoomoney - 41001303250491
brevis
Это называется Subset sum problem.
Реализаций наверное немеряно. Есть даже наивные и на php. Например, http://stackoverflow.com/a/38126705/1007620

_____________
Чатик в телеге
Владимир55
Рандомный алгоритм как-то не проходит.

Я его так организовал.

Все 500 чисел заносим в массив.

Гнерируем 30 неповторяющихся случайных чисел в диапазоне от нуля до 499.

Каждое из сгенерированных чисел рассматриваем как индекс ячейки массива. Поочередно извлекаем содержимое этих ячеек и суммируем с извлеченным ранее.

Если перебор, то генерируем новую партию случайных чисел и начинаем все заново.

По сути, это ведь то же самое, что Вы предложили?
Valick
Цитата (Владимир55 @ 8.01.2017 - 20:10)
По сути, это ведь то же самое, что Вы предложили?

нет, точнее почти тоже самое
но не надо каждый раз брать рандомные числа из массива, надо "добивать" расклад.
Надо хранить уже использованные ячейки массива, для того что бы не выбирать их повторно на определённых шагах алгоритма

_____________
Стимулятор ~yoomoney - 41001303250491
Владимир55
Цитата (brevis @ 8.01.2017 - 17:09)

Реализаций наверное немеряно. Есть даже наивные и на php. Например, http://stackoverflow.com/a/38126705/1007620

Этот код не работает. Почему - я не понимаю.

subset_sum([11.96,1,15.04,7.8,20,10,11.13,9,11,1.07,8.04,9], 20);


function subset_sum($a,$s,$c = array())
{
if($s<0)
return;
if($s!=0&&count($a)==0)
return;
if($s!=0)
{
foreach($a as $xd=>$xdd)
{
unset($a[$xd]);
subset_sum($a,$s-$xdd,array_merge($c,array($xdd)));
}
}

else
print_r($c);

}


Ошибка в первой строке:
Цитата
Parse error: syntax error, unexpected '[', expecting ')'
Быстрый ответ:

 Графические смайлики |  Показывать подпись
Здесь расположена полная версия этой страницы.
Invision Power Board © 2001-2024 Invision Power Services, Inc.