Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: Подбор суммы из множества чисел
СообщениеДобавлено: 19 сен 2018, 15:12 
Не в сети
Начинающий
Зарегистрирован:
19 сен 2018, 14:59
Сообщений: 2
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Друзья, не могу сообразить.
Подскажите как в математике или к какому разделу это правильно отнести решить такую задачу:

Есть скажем 500 чисел. И сумма. Нужно из этих чисел за минимальное количество шагов собрать эту сумму.

Благодарю!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Подбор суммы из множества чисел
СообщениеДобавлено: 19 сен 2018, 15:27 
Не в сети
Любитель математики
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 22268
Откуда: Беларусь, Минск
Cпасибо сказано: 2096
Спасибо получено:
4958 раз в 4631 сообщениях
Очков репутации: 845

Добавить очки репутацииУменьшить очки репутации
onekill
onekill писал(а):
Нужно из этих чисел за минимальное количество шагов собрать эту сумму.

То есть? Например, есть четыре числа [math]1,~3,~2,~1.[/math] Чтобы их сложить, нужно трижды выполнить сложение. Это значит, что нужно сделать три шага?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Подбор суммы из множества чисел
СообщениеДобавлено: 19 сен 2018, 15:34 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
onekill
 Заголовок сообщения: Re: Подбор суммы из множества чисел
СообщениеДобавлено: 20 сен 2018, 14:10 
Не в сети
Начинающий
Зарегистрирован:
19 сен 2018, 14:59
Сообщений: 2
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Такс. За направление большое спасибо.
Взялся пробовать. Прочитал пару статей и взяв в руки эту статью нормально понял только алгоритм 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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Подбор суммы из множества чисел
СообщениеДобавлено: 20 сен 2018, 16:03 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
onekill писал(а):
Но прошу помощи именно понять, какой способ точно поможет решить задачу в пределах ресурсов одного компьютера.

В той формулировке, что вы привели, никакой способ не поможет. Потому что NP-полная задача. Возможно, на ваши числа накладываются какие-то ограничения, но об этом вы ничего не сказали. Если случайный набор, да ещё и числа нецелые, то вполне возможно, что такого подмножества просто нет - тогда вам придётся перебирать всё. Другое дело, что что-то можно оптимизировать: отбросить часть множества, с большими, чем заданная сумма элементами; сортировать исходное множество и т.п. Но это так, мелочь.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 5 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задания на подбор чисел. №19 из базовой математики

в форуме Алгебра

lika01

24

8439

14 окт 2014, 13:30

Суммы целых чисел

в форуме Начала анализа и Другие разделы школьной математики

vlad97881

1

261

08 апр 2019, 18:24

Известные числа и суммы чисел

в форуме Теория чисел

dramatic

2

339

23 авг 2017, 10:59

Формула вычисления суммы чисел от 1 к x

в форуме Размышления по поводу и без

Yukhno

5

178

27 ноя 2019, 10:06

Распределение суммы чисел с полиномиальным распределением

в форуме Теория вероятностей

olmarin

2

220

21 июл 2017, 12:14

Делитель суммы всех предыдущих чисел

в форуме Задачи со школьных и студенческих олимпиад

Xenia1996

2

362

18 июл 2017, 00:43

Нахождение суммы произведений натуральных чисел от 1 до 9

в форуме Алгебра

PSam

3

155

25 окт 2023, 14:22

Вычислить указанные суммы целых чисел

в форуме Дискретная математика, Теория множеств и Логика

pushkinooo

2

286

30 май 2019, 12:40

Составить ряд распределения суммы случайных чисел X + Y

в форуме Теория вероятностей

Aleks70694

0

549

14 май 2014, 20:36

Вычислить указанные суммы целых чисел,как закончить

в форуме Дискретная математика, Теория множеств и Логика

pushkinooo

5

282

04 июн 2019, 13:01


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved