LINUX.ORG.RU
Форум — Development  

Задача об упаковке аниме в контейнеры


0

0

Задача: уместить несколько сериалов на наименьшее число болванок. От обычной упаковки в контейтеры она отличается дополнительными условиями:

1) каждый сериал нужно размазать по наименьшему числу дисков;

2) на одном диске может быть только один непрерывный кусок сериала (чтобы не получилось, например, что все чётные серии оказались на одном диске, а нечётные на другом, и после каждой серии диск надо менять).

Я не математик, так что киньте ссылок, откуда начинать копать. :)

← что бы почитать о libxml?
Импорт mdb в kexi →

Причем тут математика? берешь калькулятор, режешь серии на мелкие куски и пишешь подряд. чем меньше кусок, тем меньше потери свободного места.

Vinick ★★
()
Ответ на: комментарий от ero-sennin

Насколько я понимаю, задача не особо математическая.

Вариант (самый наитупейший): Пишем серии подряд, пока влезают, переходим к следующему диску. Если же сериал закончился, переходим к следующему. Результат -> минимизация "размазанности" сериала. Максимум, что тут можно соптимизировать -- перестановка порядка следования сериалов, но выигрыш от этого копеечный, а задача, ЕМНИП, переборная.

В остальных вариантах можно выиграть какие-то жалкие проценты за счет того, что каждый сериал будет размазан по куче дисков. ИМХО, оно того не стоит -- неудобно смотреть, неудобно давать диски "на посмотреть" (даешь один сериал, лишаешься нескольких), неудобно списывать сериал знакомым на их болванки (запаришься диски переставлять). При ~2р/1GB этот геморрой точно не окупается :)

watashiwa_daredeska ★★★★
()

неужели 20 рублей, потраченные на две лишние болванки, стоят затрат твоего времени?

anonymous
()
Ответ на: комментарий от watashiwa_daredeska

> Вариант (самый наитупейший): Пишем серии подряд, пока влезают, переходим к следующему диску. Если же сериал закончился, переходим к следующему. Результат -> минимизация "размазанности" сериала. Максимум, что тут можно соптимизировать -- перестановка порядка следования сериалов, но выигрыш от этого копеечный, а задача, ЕМНИП, переборная.

Хм, и правда, есть смысл на этом остановиться.

Сейчас до меня дошло, что на диски можно писать и в несколько сессий. То есть, берём один сериал, пишем на несколько болванок. На последней останется место. На это место потом дописывается начало следующего сериала. Если одна серия занимает 200-300 мегабайт, то потери будут вполне приемлемые.

ero-sennin ★★
() автор топика
Ответ на: комментарий от ero-sennin

Задача по по "укладке рюкзака" практически в чистом виде. NP-полная как уже тут заметили. Решается приближенно достаточно эффективно. В гугль.

anonymous
()
Ответ на: комментарий от anonymous

> Задача по по "укладке рюкзака" практически в чистом виде. NP-полная как уже тут заметили. Решается приближенно достаточно эффективно. В гугль.

задача об укладке рюкзака — это частный случай задачи об упаковке в контейнеры для случая, когда контейнер один. А сама задача о контейнерах, очевидно, частный случай задачи об упаковке аниме на диски. Что она NP-полная, это ёжику понятно. Я и просил накидать ссылок на разные эмпирические методы приближённого решения таких задач с дополнительными ограничениями. Или хотя бы скажите, по каким словам искать.

ero-sennin ★★
() автор топика
Ответ на: комментарий от ero-sennin

сводишь к integer linear programming

glpsol (gnu linear programming kit) умеет их решать методом branch and bound

dilmah ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← что бы почитать о libxml?
Development
Импорт mdb в kexi →