Преглед садржаја:
Дефиниција - Шта значи проблем са руксаком?
Проблем са руксаком је проблем оптимизације који се користи за илустрацију и проблема и решења. Име је добио по сценарију где је један ограничен у броју предмета који се могу сместити у руксак фиксне величине. С обзиром на скуп предмета са специфичном тежином и вредностима, циљ је да се што већи удио у ранцу добије с обзиром на ограничење тежине ранца.
Тецхопедиа објашњава Кнапсацк проблем
Проблем са руксаком је пример проблема комбинационе оптимизације, теме из математике и рачунарске науке о проналажењу оптималног објекта међу низом објеката. Ово је проблем који се проучава више од једног века и уобичајени је пример примера у комбинаторној оптимизацији, где постоји потреба за оптималним објектом или коначним решењем где исцрпна претрага није могућа. Проблем могу бити пронађени у стварном сценарију попут расподјеле ресурса у финансијским ограничењима или чак у одабиру инвестиција и портфеља. Такође се може наћи у областима као што су примењена математика, теорија сложености, криптографија, комбинаторика и рачунарска наука. То је лако најважнији проблем у логистици.
У проблему руксака, дате ставке имају најмање два атрибута - вредност предмета која утиче на њену важност и тежину или количину предмета, што је његов аспект ограничења. Пошто исцрпна претрага није могућа, проблем се може разбити на мање под-проблеме и покренути их рекурзивно. То се назива оптималном под-структуром. Ово се односи на само један предмет истовремено и тренутну тежину која је још увек доступна у ранцу. Решивач проблема треба само да одлучи да ли ће узети предмет или не на основу тежине која се још може прихватити. Међутим, ако се ради о програму, поновно рачунање није независно и узроковаће проблеме. Овде се могу применити динамичке технике програмирања. Решења за сваки подпроблем се чувају тако да би се рачунање морало догодити само једном.
