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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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




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

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

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

Благодарю!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Подбор суммы из множества чисел
СообщениеДобавлено: 19 сен 2018, 15:27 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июл 2011, 08:33
Сообщений: 17899
Откуда: Беларусь, Минск
Cпасибо сказано: 1255
Спасибо получено:
3845 раз в 3563 сообщениях
Очков репутации: 718

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Подбор суммы из множества чисел
СообщениеДобавлено: 19 сен 2018, 15:34 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 4463
Cпасибо сказано: 74
Спасибо получено:
954 раз в 868 сообщениях
Очков репутации: 213

Добавить очки репутацииУменьшить очки репутации
Вернуться к началу
 Профиль  
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 
Не в сети
Beautiful Mind
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 1602
Cпасибо сказано: 115
Спасибо получено:
282 раз в 259 сообщениях
Очков репутации: 36

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

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

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

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

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

lika01

24

7471

14 окт 2014, 13:30

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

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

vlad97881

1

59

08 апр 2019, 18:24

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

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

dramatic

2

173

23 авг 2017, 10:59

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

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

Aleks70694

0

376

14 май 2014, 20:36

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

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

olmarin

2

95

21 июл 2017, 12:14

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

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

Xenia1996

2

170

18 июл 2017, 00:43

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

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

DjoyceGraham

2

1728

22 апр 2011, 15:16

Алгебра: док-во множества рац. чисел

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

evg1401

2

144

07 май 2018, 20:59

Представление чисел в виде суммы двух и более квадратов

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

Katherina

2

878

28 сен 2012, 10:26

Несчетность множества рациональных чисел в (0; 1)

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

CO3HAHUE

4

135

24 янв 2019, 15:17


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



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

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


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

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

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

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