0
$\begingroup$

I decided to try my hand at solving the knapsack problem.

My idea involved generating $i$ tables, where $i: 1 \le i \lt n$, and each cell of an $i$ table contains one of the possible sums of the objects to fit into the knapsack. The $i$ tables will then be sorted. Then for each of the $k$ numbers to be tested, I'll run a binary search on the sorted arrays.

I realised that there may be sums which repeat. I feel like recording them will be unnecessary waste of space.

So I want to determine if for any new number $k$ to be added to the list, if $k$ is a duplicate of any number in the list. It is trivial to just search the list, but this is too inefficient, and takes $O(n^2)$ operations, making the trade off with space complexity a bad deal.

I wanted a linear time algorithm for solving this problem. I thought of a function, which takes in inputs, and the function is such that if any new input is the same as a previous input, the function will provide a certain known output. This function should work in constant time or at worst, logarithmic time.

I have tried several means of constructing the function but they failed.

$\endgroup$
4
$\begingroup$

Use any efficient set data structure, based e.g. on hashtables or balanced search trees.

Keep in mind that such optimizations are dwarfed by the exponential nature of any algorithm I assume you will come up with.

That said, you may want to check out pseudo-polynomial algorithms for Knapsack, and problem variants that have polynomial-time algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.