I have a distance to get to, and square tiles that have a cost and length. EX: a 1 unit block that costs 1 unit to purchase.
So if I was trying to get 10 units away. I would require 10 of the 1 unit blocks at that point for a total cost of 10.
So another example would be a distance of 10 units away except I have two tiles to pick from of [1,1], [5,4], [x,y], x = length, y = cost.
The cheapest cost would be 8, (2 of 5 blocks = 10 distance).
So, at first I thought this would be a shortest path problem, but seeing how I can re-use tiles that didn't work out the best.
I then tried to implement a rod-cutting algorithm, using the length of the rod as distance and the price for the length of cuts. This algorithm though kept trying to maximize the distance, which wasn't what I wanted.
My final method, was to divide the cost by length for each tile to find the most cost efficient tile (shown below). This worked for about 9% of my unit-tests, it was failing most because it couldn't see that it might be more cost effective to use a more expensive tile, etc.
I started with a greedy algorithm using cost / length for most efficient cost tiles, when I couldn't get that to work. I moved towards a dynamic programming algorithm using the cutting rod example.
This required a lot of hacky work, since I didn't really want the maximized value via cutting. I wanted the minimal cost value of that distance, though it also only had about a 2% success rate.
I then went into recursion, with help from another tip. Using a tiny little Tile class to help me pass variables around, this had lots of success with my self test values, but once again only had a 10% success rate.
So after trying DFS, Rod-Cutting, Recursion, and Dynamic Programming. I am lost. Did I overlook one of these algorithms?