Re:JQuery plugin to arrange images using knapsack algorithm
by gauravsc on Tuesday April 24, 2012 @05:34AM
(#3883125)
We are using Dynamic programming and you are correct, knapsack is a problem but since the most common solution(and widely used) is using DP, we sometimes intermittently use the term Knapsack algorithm with DP algorithm to solve Knapsack problem.
Re:JQuery plugin to arrange images using knapsack algorithm
by ColinWright on Tuesday April 24, 2012 @05:36AM
(#3883133)
Right, that makes sense. Thank you.
What would happen if I encoded a large integer factorization instance into a Knapsack Problem and called your system?
Re:JQuery plugin to arrange images using knapsack algorithm
by DennisP on Tuesday April 24, 2012 @07:35AM
(#3883432)
Given that it's a jquery plugin, you'd probably get a "script on this page is running slowly" message.
Re:JQuery plugin to arrange images using knapsack algorithm
by vog on Wednesday April 25, 2012 @06:50AM
(#3888510)
This answer completely misses the point. Of course the algorithm could run "forever", thus triggering browser timeouts.
But it could as well terminate early, providing a suboptimal but fast solution.
To the best of my knowledge there is no such thing as "The Knapsack Algorithm." (Except in the (now broken) Knapsack Public Key Encryption system)
The only references I've found in a quick search either incorrectly use the term "Knapsack Algorithm" when they actually mean "Knapsack Problem," or they simply refer to the obvious depth-first recursive search.
So the question remains - what algorithm are you using? Depth-first search? Dynamic programming? Greedy algorithm with heuristics and early cut-off? Simulated Annealing? Hill-Climbing? All of these can be used to find good solutions to an instance of the Knapsack Problem.
The auxiliary question: Given that the Knapsack Problem has been shown to be NP-Complete, what will your code do when given a hard instance?