Dinamichno optimirane 1

Zdraveite na vsichki. Veroiatno vaprosa ne e samo za tozi forum no vse pak koito ima jelanie neka pogledne.
Ot niakolko dena se macha sas slednata zadacha. Shte dam primer s files i zapis varhu diskove. Dadeni sa 100 files vseki s razlichna golemina (30, 40, 60, 70, etc). Celta e pri izbor na niakakva chast ot tiah (primerno 60) da se razpredeliat v opredelen broi diskove s ramer ot 200 MB primerno. Celta e diskovete koito se poluchat (1,2,3 broia) da sa maksimalno zapalneni).
Niakoi ima li idei kak moje da se napravi ili dali ima niakakvo gotovo reshenie.
Mersi predvaritelno.

Викат й по-сто начина, май най-популярният е 'Задача за раницата': раницата побира еди колко си килограма, дай да я натъпчем максимално. Аз вчера я решавах тази задача, но беше за музика и дискове по 700M :-)
Накратко казано това е задача която няма леко оптимално решение - трябва да изгенерираш всички подмножества, които са ( пак накратко казано ) МНОГО. Може да се поорежат, но пак остават Много.
Обаче има една евристика, която работи доста добре - буташ името на файла в колона 'A', а размера в колона 'B', на Ексела. Сортираш по намаляващ размер и гледаш да удовлетвориш по-големите. Получават се удивително добри резултати.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Имаш ли статистика/данни колко добро е полученото решение спрямо оптималното?

I think its kinda funny I think its kinda sad the dreams in which Im dying are the best Iv ever had

Simplex metoda. Opitai s nego. No poneje e wajen metod i se izpolzwa pri reshawane na mnogo zadachi, do sega ne sam nameril free w Internet.

задача за симплекс метод.....тук се търси максимален БРОЙ НУЛЕВИ ЕЛЕМЕНТИ (неизползвани дискове), а не стойност на линейна функция.

Задачата наистина има добро решение с динамично оптимиране.

Подробности (на български) за метода на динамичното оптимиране и за задачата за раницата можеш да намериш тук:

[линк]

Goddam money. It always ends up making you blue as hell.

няма нищо общо с описаната в материала "задача за раниЦАТА". Тя е ясна и може да се реши със симплекс метод с условие за целочисленост, там ясно е очертана целевата функция, на която търсим максим и ограничителните условия - да се поберат предметите в раниЦАТА (кои предмети да изберем). Задачата от постинга е съвсем друга - в КОЛКО РАНИЦИ най-малко можем да поберем всички зададени предмети. Двете задачи нямат нищо общо

бъркаш се, общата задача за раницата (като написах на човека, но в друг форум) е NP-пълна задача, а това че в частните случаи на този проблем може да се минава с greedy или други алгоритми е съвсем друга работа ...

към който човека е дал линк:

Дадена е раница с вместимост M килограма и N предмета, всеки от които се характеризира с две числа mi (тегло) и ci (ценност). Да се избере такова множество от предмети, чиято сумарна ценност е максимална, а сумата от теглата им не надвишава M. Числата M, N, ci и mi са естествени.

Съгласи се, че така зададена задачата е меприложима за решаване на задачата от постинга

П.С Ако имаш алгоритъм, приложим за решаване на задачата от постинга (или линк към него) можеш да го постнеш

Прави сте, че не съм разбрал условието. Извинявам се за загубеното време.

Но все пак в задачата не се иска да се минимизира броя на дисковете, а се иска, доколкото разбрах, при фиксиран брой дискове да се разпредели информацията между тях.

За нея не знам решение, но изглежда интересна и си заслужава да се помисли.

Goddam money. It always ends up making you blue as hell.

То и условието не е особено ясно...

Тия дискове наистина фиксиран брой ли са?

А не може ли да се приеме, че цената = теглото и да се реши подобно на раницата?

говорех за общия случай

ето тука изкопах някакъв линк за пример [линк]

разбира се, това е единичен случай, но лесно можеш да потърсиш и да разгледаш генерализацията за multiple knapsack problem

мисълта ми бе, че ако единичния случай е пълната задача (NP-пълна), то хубаво решение в единичния, а камо ли и в множествения случай, едва ли ще има

Не е ли тва, което се иска?

[линк]

е това е още по-общия проблем

то пише отдолу - See also knapsack problem, cutting stock problem, optimization problem, strip packing, set packing.

човека е написал "Shte dam primer s files i zapis varhu diskove", т.е. каква му е истинската цел и задача не е ясно, а от примера първото, за което се сетих, бе задачата с раницата

мда аз там кликнах :)

пообъркал съм се - бин пакинга не е с цели числа.