SYКорзина = рюкзак. T.е. есть рюкзаки вместимoстью N упаковок и 5 упаковок с разным количеством товара которые нужно разложить по рюкзакам.Алгоритмы для задачи о рюкзаке рассчитаны на один рюкзак а не несколько.
И они максимизируют ценность с жестким лимитом на вместимость.
В случае ТС ничего страшного не будет, если какая-то корзина чуть превысит лимит (если мы минимизируем дисперсию).
SYКак именно разложить требует уточнения задачи - набить максимально, т.е. (100), (1,2,3,10), пустой (минимизация числа корзин)Если минимизируем число корзин (странный критерий если цель распределить по n корзинам), то почему бы не засунуть всё в одну.
watsonв любом случае, если кто-то напишет на sql, будет любопытно взглянуть. :)А как ты будешь проверять если не в состоянии озвучить критерий оптимальности?
Минимизация дисперсии корзин требует слишком большой вычислительной сложности.
Полный перебор - корзины в степени упаковки. Его наверняка можно как-то сократить, но все равно будет очень долго.
Соответственно можно смотреть на приближенные распределения, например
1) либо совсем забить на число бананов и распределять по mod(ora_hash(упаковка), число корзин)
2) либо кумулятивную сумму распределять по бакетам
(более-менее нормально работает если нет упаковок больших чем размер корзины.
если такие есть - их предварительно можно определить в отдельные корзины)
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
with c(id, pack, amount)
as
(
select 0, 'pack_0', 20 from dual
union all
select 1, 'pack_1', 10 from dual
union all
select 2, 'pack_2', 3 from dual
union all
select 3, 'pack_3', 2 from dual
union all
select 4, 'pack_4', 1 from dual
),
t as
(select c.*,
sum(amount) over (order by amount) x,
sum(amount) over () total
from c)
select t.*,
width_bucket(x, 0, total + 1e-10, 3) bkt0,
-- или что то же самое
ceil(x / (total / 3)) bkt1
from t
order by 1;
ID PACK AMOUNT X TOTAL BKT0 BKT1
---------- ------ ---------- ---------- ---------- ---------- ----------
0 pack_0 20 36 36 3 3
1 pack_1 10 16 36 2 2
2 pack_2 3 6 36 1 1
3 pack_3 2 3 36 1 1
4 pack_4 1 1 36 1 1
Все будет уже не так симпатично если 20 заменить на 30 или вообще 100.
