Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 5 ] |
|
Автор | Сообщение | |
---|---|---|
onekill |
|
|
Подскажите как в математике или к какому разделу это правильно отнести решить такую задачу: Есть скажем 500 чисел. И сумма. Нужно из этих чисел за минимальное количество шагов собрать эту сумму. Благодарю! |
||
Вернуться к началу | ||
Andy |
|
|
onekill
onekill писал(а): Нужно из этих чисел за минимальное количество шагов собрать эту сумму. То есть? Например, есть четыре числа [math]1,~3,~2,~1.[/math] Чтобы их сложить, нужно трижды выполнить сложение. Это значит, что нужно сделать три шага? |
||
Вернуться к началу | ||
swan |
|
|
Вернуться к началу | ||
За это сообщение пользователю swan "Спасибо" сказали: onekill |
||
onekill |
|
|
Такс. За направление большое спасибо.
Взялся пробовать. Прочитал пару статей и взяв в руки эту статью нормально понял только алгоритм 2, самый простой, то есть перебора. Пока, честно говоря, прочитав 2 раза не полностью понял остальные. Путём перебора мою задачу не решить, это точно. Потому что моё n[math]^{200}[/math] на числах от 1 до 1 000 000 так не перебрать. Буду признателен за пояснение, какой метод точно поможет мне решить данную проблему. Опишу подробно ещё раз: Есть 200+ чисел от 1 до примерно 1 000 000 с 2 знаками после запятой. Необходимо найти подмножество из множества чисел n равное определённой сумме. Например есть 200 чисел вида: 132242.23, 21.33, 5752.78, 34, 1295.33, 936486.50, ..., n200. И сумму которую необходимо составить из части этих чисел. Например 1809675,35 Простите за кривые примеры. Тексты и статьи честно читал. Но прошу помощи именно понять, какой способ точно поможет решить задачу в пределах ресурсов одного компьютера. А сам подходящий способ я тогда уже заковыряю до победного. |
||
Вернуться к началу | ||
Booker48 |
|
|
onekill писал(а): Но прошу помощи именно понять, какой способ точно поможет решить задачу в пределах ресурсов одного компьютера. В той формулировке, что вы привели, никакой способ не поможет. Потому что NP-полная задача. Возможно, на ваши числа накладываются какие-то ограничения, но об этом вы ничего не сказали. Если случайный набор, да ещё и числа нецелые, то вполне возможно, что такого подмножества просто нет - тогда вам придётся перебирать всё. Другое дело, что что-то можно оптимизировать: отбросить часть множества, с большими, чем заданная сумма элементами; сортировать исходное множество и т.п. Но это так, мелочь. |
||
Вернуться к началу | ||
[ Сообщений: 5 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Задания на подбор чисел. №19 из базовой математики
в форуме Алгебра |
24 |
8439 |
14 окт 2014, 13:30 |
|
Суммы целых чисел
в форуме Начала анализа и Другие разделы школьной математики |
1 |
261 |
08 апр 2019, 18:24 |
|
Известные числа и суммы чисел
в форуме Теория чисел |
2 |
339 |
23 авг 2017, 10:59 |
|
Формула вычисления суммы чисел от 1 к x
в форуме Размышления по поводу и без |
5 |
178 |
27 ноя 2019, 10:06 |
|
Распределение суммы чисел с полиномиальным распределением
в форуме Теория вероятностей |
2 |
220 |
21 июл 2017, 12:14 |
|
Делитель суммы всех предыдущих чисел | 2 |
362 |
18 июл 2017, 00:43 |
|
Нахождение суммы произведений натуральных чисел от 1 до 9
в форуме Алгебра |
3 |
155 |
25 окт 2023, 14:22 |
|
Вычислить указанные суммы целых чисел | 2 |
286 |
30 май 2019, 12:40 |
|
Составить ряд распределения суммы случайных чисел X + Y
в форуме Теория вероятностей |
0 |
549 |
14 май 2014, 20:36 |
|
Вычислить указанные суммы целых чисел,как закончить | 5 |
282 |
04 июн 2019, 13:01 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |