|
Интересное распределение, задачка | ☑ | ||
---|---|---|---|---|
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) Тут важен порядок не в смысле упорядоченности, а в смысле порядка количества: сотни, тысячи, миллионы...
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |