dynamic programming - Can 01Knapsack algorithm with solution printed using O(n) space? -


with dynamic programming, 01 knapsack can solved using formula:

f(v) = max(f(v), f(v-cost(i)+w(i)) v reverse enumeration.

but if want record item put knapsack, need 2 dimensional array record item index.

i'm not sure can 01knapsack use o(n) space solution of items put in knapsack?

it true solution dp n states can reconstructed @ o(n) additional memory. way create additional array of same size states array , store move did each states. in case of particular problem, have record if f(v) or f(v-cost(i)+w(i)) optimal.


Comments

Post a Comment

Popular posts from this blog

toolbar - How to add link to user registration inside toobar in admin joomla 3 custom component -

im trying write component admin side , need add user creation. dont want duplicate existing codes add link. know how add task not simple link toolbar. thx help. if wanting button opens new user screen can try in component: $bar = jtoolbar::getinstance('toolbar'); $bar->appendbutton('link', 'users', 'new user','index.php?option=com_users&task=user.add'); you need add view.html.php file wherever you're creating toolbar. is need?
Read more

linux - disk space limitation when creating war file -

i have 1 gb disk space limitation hosting app , have used 700mb of it. however want create war file directory big (around 600mb) using command : jar -cvf root.war folderpath that's why encounter quota limitation , can't following. i'm looking way delete folder content when it's applying archive conserve disk space take note can't install zip tool in ssh shell ~ the code works on test directories, test first anyway, deletes files. it's not efficient. assumptions: 300mb free space, in destructively compress 600mb folderpath directory. none of files big -- if file in folderpath 300mb or larger, fail. notes: if ' $out ' file exists, nothing. first find pipes file list while , if ' $out ' doesn't exist in loop, create it, don't update -- if does exist, update it. each pass adds 1 more file, deletes unless file directory. after loop finishes delete empty directories too. unset u ; in=folderpath ; out=roo...
Read more