1

I have a project in my University I think the problem should be resolved by knapsack algorithm.

We have quadratic area with size:

 n x n.

The size is coming from the command line. In the input file we are storing in the lines real numbers. Every of the numer is diameter(called "d") of the circle which we are going to set in our area. In every case the n size is greater then diamater. The file is containing lots of numbers so we have lots of cases to choose.

We need to create method "pack()" and implement inside the method the code which will get any circles from the file then will put them inside the area in the way that the area will be occupied with as many circles as possible( We need to occupied the highest possible value for n-area with the circles ). That means we are looking for those of data(circles) whose will replace the biggest part of our area.

I was thinking about that problem but didn't find any solutions. From my perspecive I need to modify knapsack algorithm, but no idea how. In my option the most important part will be to choose the alogrithm .

Could you guys point me to the proper algorithm? Any tips will be very appreciate, cause I'm wasted in that problem.

code_pretty
  • 145
  • 3
  • 15
  • Why do you think it is a knapsack problem? – Lior Kogan Mar 29 '14 at 14:32
  • 1. firsty the profersor said that will be proper algorithm to resolve problem . 2. Seconly I cannot see anything better – code_pretty Mar 29 '14 at 15:15
  • Related: http://stackoverflow.com/questions/13339615/packing-different-sized-circles-into-rectangle-d3-js – Lior Kogan Mar 29 '14 at 16:55
  • Do you mean "We need to find the highest possible value for **n^2**-area with the circles"? – j_random_hacker Mar 29 '14 at 22:18
  • I don't see exactly how this translates to a knapsack problem, but here are a couple of suggestions: (1) Although it's still a hard problem to pack squares optimally, this seems easier than packing circles, so I suggest trying to pack the bounding boxes of the circles first and see how far you get with that. (2) Look for symmetries that reduce the search space. Here, any solution can be horizontally and/or vertically flipped to get another solution of the same size. What that means is that you need only consider solutions in which the largest circle is in the top-left quarter. – j_random_hacker Mar 29 '14 at 23:02

0 Answers0