|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 11 Oct 2001 01:30:13
To : Alex Astafiev
Subject : Re: Распpеделение файлов по CD
--------------------------------------------------------------------------------
Alex Astafiev wrote:
> ...
> > Есть такая задачка:
> > Есть N файлов, (pазных pазмеpов < ёмкости CD болванки) и k CD
> > болванок (фиксиpованного pазмеpа). Hадо наиболее оптимальным
> > обpазом "pаспихать" файлы по болванкам. Под оптимyмом
> > подpазyмевается что-бы как можно большее кол-во болванок было
> > забито с свободным местом <=10Mb.
>
> Кстати, интересная задача. Ее можно перефразировать так:
>
> Как - то раз мне на спектруме понадобилось загружать звуковые сэмплы
> произвольной длинны 1..16384 байта в страницы памяти.
>
> нужно было решить ту же задачу, то есть заполнить страницы памяти размером в
> 16K по максимуму, разместив сэмплы как можно плотнее.
>
> Я эту задачу как-то решил, написав на ассемблере Z80, но уже не помню как. И
> очень хотелось бы узнать как ее решать математически. Раскрой?
В том то и дело, что твоя задачка мало похожа не его задачку. Тебе нужно
_минимизировать_ количество использованных страниц памяти, а OP хочет
_максимизировать_ количество использованных CD (при этом надо по
возможности соблюсти дополнительное огоаничение: свободного места не
каждом CD должно остаться не больше 10 Мб).
Я бы эту задачку назвал "Задачей о прапорщиках" (по мотивам известного
анекдота):
Прапорщикам поручили вывезти мусор со склада (конечное количество
обломков различного веса). Они решили воспользоваться этим поручением
для того, чтобы стибрить со склада тачки (все тачки одинаковые и
обладают ограниченной грузоподъемностью). Каким образом им загрузить
тачки так, чтобы количество вывозимых тачек оказалось максимальным, и
при этом так, чтобы каждая вывозимая тачка была загружена не менее чем,
скажем, на 90% (чтобы не заподозрили).
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: Very good (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
