Цитата(dials @ 26.1.2006, 14:26  ) |
Поэтому, при наполнении блоков, необходимо учитывать ещё и параметр k. Как в таком случае быть? |
Это всего лишь параметр кратности. Дополнительное ограничение.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм размещения данных с тремя параметрами |
| Автор: dials 26.1.2006, 11:18 |
| Может быть кто-то сможет помочь в создании алгоритма... Вход: m - количество блоков.Каждый блок имеет свой размер n - ролик(размер) k - некий параметр ролика, который изменяется в зависимости от предыдушего размещения в блоке. Известно, что для каждого блока m, есть возможность размещения некоторых роликов n: У нас есть допустим ролики вида: n1(5 байт),n2(6 байт),n3(10 байт),n4(15 байт),n5(3 байта) Тогда: Номер блока(m) |Размер блока |Допустимые ролики для блока 1 |15 |n1,n3,n4 2 |26 |n2,n1,n4 3 |30 |n1,n4,n5,n3 Выход: Необходимо разместить в каждом блоке m(i) набор роликов так, чтобы сумма размера роликов максимально стремилась к размеру блока(т.е. Summ(набора роликов)<=Размер блока) Т.е. для m1(15)=n1,n3 или n4 Доп.условие: Параметр k: Каждый ролик имеет данный параметр, он означает сколько раз может ролик появлятся в блоках: Если для n1 k=1 значит, что если этот ролик появился в блоке m=1, он более не может появится нигде. Если для n1 k=3 значит, что этот ролик может появится не более 3х раз. Такая задача... Насколько я понимаю это NP-полная задача...Простым, тупым перебором решать её нереально по времени,т.к. m - порядка 20, n - порядка 1000. |
| Автор: Akina 26.1.2006, 11:52 |
| Это - типичная "задача о рюкзаке". Наполнение кучи рюкзаков (блоки) кучей предметов (ролики). |
| Автор: dials 26.1.2006, 14:26 | ||
Не совсем. Это была бы типичная задача, при условии, что у нас есть m - блоков и n - ролики. Но у нас есть ещё у каждого ролика k - количество появлений ролика в наборе блоков([не больше, не меньше, точно] раз). Поэтому, при наполнении блоков, необходимо учитывать ещё и параметр k. Как в таком случае быть? |
| Автор: Akina 26.1.2006, 14:44 |
| Все это не влияет. Форма предметов и даже количество измерений - тоже не влияет. Основа одна и та же. |
| Автор: podval 26.1.2006, 22:22 | ||
Это всего лишь параметр кратности. Дополнительное ограничение. |