Имя: Пароль:
1C
 
Интересное распределение, задачка
0 Ibsen
 
24.01.18
12:47
Подскажите, может ссылкой киньте на алгоритм. Задача в следующем.
Есть массив цен товаров в кол-ве 400 шт. у Каждого своя цена. Итоговая сумма всех товаров например 100 000.
Нужно распределить товары по 3 группам так, чтобы в первой группе были товары на сумму 20 тыс. во второй на 30 тыс. и в третей на 50 тыс. ровно.
Примеры примерные, т.к. кол-во товаров гораздо больше и суммы тоже
1 drcrasher
 
24.01.18
12:48
и в чем сложность?
2 Лодырь
 
24.01.18
12:49
Прям ровно? или почти ровно?
3 Злопчинский
 
24.01.18
12:50
ну например в том, что в общем случае группы ровно по 20-30-50 тыс не получится
4 drcrasher
 
24.01.18
12:50
(2) я сильно сомневаюсь, что получится прям ровно
5 Ibsen
 
24.01.18
12:51
(2) прям ровно.
т.е. суммы товаров точно могут так собраться, вопрос каким алгоритмом их подобрать
6 Asmody
 
24.01.18
12:51
7 AlexYAT
 
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?
11 Ibsen
 
24.01.18
12:58
(10) в данный момент 314 строк по задаче
12 Ibsen
 
24.01.18
12:58
(9) порядок не важен, главное итоговая сумма
13 Asmody
 
24.01.18
13:00
(12) Тут важен порядок не в смысле упорядоченности, а в смысле порядка количества: сотни, тысячи, миллионы...
2 + 2 = 3.9999999999999999999999999999999...