No, it doesn't suffice. You are using an undescribed and unspecified algorithm to solve a specific instance of the Knapsack Problem.
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?
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.
Great idea! However, the term "knapsack algorithm" is quite misleading.
There is the "knapsack problem", but there are various different algorithms to solve it. Which of those has been used? Why this and not another algorithm? All those questions are concealed behind the squishy term "knapsack algoritm".
We have used Knapsack 0-1 algorithm, since in our case images had different widths but the same height, we wanted to fit in as many images as possible so that they fit in the best way possible. We gave value 1 to each image and weight equal to width and use the total width of container of images as the maximum weight allowed.
Well as far as my knowledge goes, any sequence of steps to solve a problem is an algorithm(some are simple algorithms and some are complex). In our case we couldn't use fractional knapsack since we couldn't break images.
So which algorithm did you use to solve the Knapsack 0-1 problem? Via Dynamic Programming? Or using the Meet-in-the-Middle Algorithm? Or a greedy approximation algorithm?
The Google+ and Google Image Search will resize and crop the image by width to fit a specified row, greedily optimizing for the maximum number of images per row.
Interesting you bring up [1] because I used a variation of that technique in my own site [2].
You can greatly simplify things if you resize all the images on the backend to the same width, then all you have to do is crop in the frontend to the minimum height in a row.
The trade off is the distortion happens by height rather than width, so you could end up cutting off someones head in a photo-gallery.
My patchwork solution now is to approximate the cropping that would be done in the rule of 3rds with a certain offset (so we lose dead space at the top).
A better technique would be to dynamically determine where a face was in the picture, and center on that. This plugin might help but you'd be better off passing that information from the backend. [3]
Whipped up a quick example, it seems to re-order the images in a way to fit the most it can on each row given the width constraints and the width of each image - http://jsfiddle.net/vXbCY/
Plugin co-author here: One more possible extension of this algo would be to use value of each image equal to the weight of each image. This would ensure best fit and would be one more way to make things look beautiful and arranged.
Hi frooxie, in that example there are 2 containers. #container1 is without plugin, and #container2 is with the plugin. Try scrolling in the iframe and you will see the arranged images.
30 comments
[ 4.2 ms ] story [ 77.6 ms ] threadI understand how arranging images may be a "knapsack problem" but I can't pinpoint what the algorithm is supposed to be.
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?
What would happen if I encoded a large integer factorization instance into a Knapsack Problem and called your system?
But it could as well terminate early, providing a suboptimal but fast solution.
There is the "knapsack problem", but there are various different algorithms to solve it. Which of those has been used? Why this and not another algorithm? All those questions are concealed behind the squishy term "knapsack algoritm".
We adapted the script below for http://current.openphoto.me/photo/list --- curious to check this out as well.
http://www.techbits.de/2011/10/25/building-a-google-plus-ins...
The Google+ and Google Image Search will resize and crop the image by width to fit a specified row, greedily optimizing for the maximum number of images per row.
Interesting you bring up [1] because I used a variation of that technique in my own site [2].
You can greatly simplify things if you resize all the images on the backend to the same width, then all you have to do is crop in the frontend to the minimum height in a row.
The trade off is the distortion happens by height rather than width, so you could end up cutting off someones head in a photo-gallery.
My patchwork solution now is to approximate the cropping that would be done in the rule of 3rds with a certain offset (so we lose dead space at the top).
A better technique would be to dynamically determine where a face was in the picture, and center on that. This plugin might help but you'd be better off passing that information from the backend. [3]
[1] http://www.techbits.de/2011/10/25/building-a-google-plus-ins...
[2] http://www.picociti.com
[3] http://facedetection.jaysalvat.com/
That doesn't seem like a good idea just to arrange some images (battery killer?).
How is the performance on this one?