0

I'm new to Javascript and Stack Overlow and therefore apologize beforehand if this is a simple problem and/or stupid question. I've tried finding the answer myself but am getting nowhere.

I have an idea to develop a web page that could provide the user a number of suggestions on which tiles to buy, depending on the users specified floor size. For example, if the user input that his/her floor is 100x100, the page should suggest that he/she could either go with 5 tiles which are 20x100, or 2 tiles which are 50x100 and so on.. The dimensions of tiles would ideally be located in a .csv so that it could be updated manually.

The problem is that I dont even know where to start, and having googled quite a bit I understand that this could be some sort of Knapsack dilemma. Does anyone have the time to point me in the right direction?

Best regards Tomas

tomjo
  • 13
  • 2
  • So you need to provide all available options of tiles that can fit to floor size, right? Can your customer cut tiles? Can tiles be turned sideways? – andnik Jan 19 '19 at 23:02
  • Exactly! The tiles can be turned sideways but not cut. – tomjo Jan 20 '19 at 05:28

1 Answers1

0

I cannot find exact solution for you, but you may look into several links below. I don't think it's Knapsack problem, maybe it's closer to Tiling Problem, but it is definitely Dynamic Programming area.

Maybe you can modify Euclid's algorithm to use rectangles instead of tiles, look at Tiling Rectangle With Squares Using Euclids Algorithm and The Most Efficient Way To Tile A Rectangle With Squares.

Also there are some similar (but not same) problems discussed on StackOverflow: Algorithm to 'count the number of ways a floor of size 5*N can be filled with tiles of sizes 1*5 and 2*5' and Tiling different size rectangles

Hope that helps a little.

andnik
  • 2,405
  • 2
  • 22
  • 33