Вход | Регистрация


Интересное распределение, задачка

Интересное распределение, задачка
Я
   Ibsen
 
24.01.18 - 12:47
Подскажите, может ссылкой киньте на алгоритм. Задача в следующем.
Есть массив цен товаров в кол-ве 400 шт. у Каждого своя цена. Итоговая сумма всех товаров например 100 000.
Нужно распределить товары по 3 группам так, чтобы в первой группе были товары на сумму 20 тыс. во второй на 30 тыс. и в третей на 50 тыс. ровно.
Примеры примерные, т.к. кол-во товаров гораздо больше и суммы тоже
 
 
   drcrasher
 
1 - 24.01.18 - 12:48
и в чем сложность?
   Лодырь
 
2 - 24.01.18 - 12:49
Прям ровно? или почти ровно?
   Злопчинский
 
3 - 24.01.18 - 12:50
ну например в том, что в общем случае группы ровно по 20-30-50 тыс не получится
   drcrasher
 
4 - 24.01.18 - 12:50
(2) я сильно сомневаюсь, что получится прям ровно
   Ibsen
 
5 - 24.01.18 - 12:51
(2) прям ровно.
т.е. суммы товаров точно могут так собраться, вопрос каким алгоритмом их подобрать
   Asmody
 
6 - 24.01.18 - 12:51
   AlexYAT
 
7 - 24.01.18 - 12:51
(0) Похоже на задачу рюкзака.

Задача о рюкзаке (англ. Knapsack problem) — дано предметов, предмет имеет массу и стоимость . Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины (вместимость рюкзака), а суммарная стоимость была максимальна.
   Лодырь
 
8 - 24.01.18 - 12:52
(7)Она и есть. Задачу о рюкзаке надо решить 3 раза подряд, насколько я понимаю. Но с точным решением ) Так что нафиг задачу в такой формулировке.
   Лодырь
 
9 - 24.01.18 - 12:54
(5) Порядок штук товара какой?
   Лодырь
 
10 - 24.01.18 - 12:55
В смысле 400 - это от фонаря? или является ориентиром для понимания размерности? Или на самом деле это будет 400000?
 
 Рекламное место пустует
   Ibsen
 
11 - 24.01.18 - 12:58
(10) в данный момент 314 строк по задаче
   Ibsen
 
12 - 24.01.18 - 12:58
(9) порядок не важен, главное итоговая сумма
   Asmody
 
13 - 24.01.18 - 13:00
(12) Тут важен порядок не в смысле упорядоченности, а в смысле порядка количества: сотни, тысячи, миллионы...

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует