And of course, once you have the complete table, then you also have found the solution to knapsack because once you have the complete table, you just start out in the right-most column and then go to the left, to the left, to the left, to the left, and each time, you look through each column and find what is the minimum size that I would need to achieve exactly this value and once you find a size that is at most as large as your container you would be done. So constructing this table here solves knapsack. Now, my question, the second quiz is of course the time required to build this table. Is that time 2^n given that we have n objects here, is that time O(2^nn) or is that time O(nv)?

Time To Build The Table – Intro to Theoretical Computer Science
Tagged on:                         

Leave a Reply

Your email address will not be published. Required fields are marked *