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

Математический форум 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
Сообщений: 17625
Откуда: Беларусь, Минск
Cпасибо сказано: 1228
Спасибо получено:
3764 раз в 3484 сообщениях
Очков репутации: 712

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

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

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

Добавить очки репутацииУменьшить очки репутации
Вернуться к началу
 Профиль  
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
Сообщений: 1351
Cпасибо сказано: 94
Спасибо получено:
245 раз в 224 сообщениях
Очков репутации: 35

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

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

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

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

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

lika01

24

7300

14 окт 2014, 13:30

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

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

dramatic

2

154

23 авг 2017, 10:59

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

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

Xenia1996

2

152

18 июл 2017, 00:43

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

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

olmarin

2

83

21 июл 2017, 12:14

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

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

Aleks70694

0

367

14 май 2014, 20:36

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

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

DjoyceGraham

2

1656

22 апр 2011, 15:16

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

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

evg1401

2

123

07 май 2018, 20:59

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

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

Katherina

2

852

28 сен 2012, 10:26

Несчетность множества действительных чисел

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

vlad777

5

528

07 ноя 2014, 15:51

Счётность множества действительных чисел?

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

Timofey-p

10

210

26 дек 2017, 10:01


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



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

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


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

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

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

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