shortest cost tiling of path to x distance

Question

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?

Answer 1

You're heading a good direction with dynamic programming, but you haven't set up the set of subproblems quite right just yet. Don't give up on it yet. Instead, you should keep exploring some more candidate sets of subproblems.

The art of dynamic programming lies in picking the right set of subproblems, and then identifying a suitable recurrence relation in terms of those subproblems. Sometimes you'll have to try several possible ways of decomposing into subproblems before you find something that works, so don't give up if your first try is not a success!

Here are some hints to help you:

• When one of your inputs is an array, you can try using "the set of prefixes of the array" as your set of subproblems. In other words, if the input is an array A[0..n-1], your subproblems can be all of the prefixes A[0..j-1], where j=0,1,2,..,n-1 (this gives n subproblems).

• When one of your inputs is a non-negative integer, you can try using "the set of non-negative integers no larger than the input" as your set of subproblems. In other words, if the input is a non-negative integer m, your subproblems can be all of the integers i, where i=0,1,2,..,m.

• When you have two inputs, there are some possibilities to choose a set of subproblems. One way is to hold one of the inputs fixed and consider all subproblems for the other input. Another way is to choose all pairs of subproblems (if $S$ is the set of subproblems for the first input, and $T$ is the set of subproblems for the second input, use $S \times T$ as your set of subproblems).

Also, you set up your dynamic programming implementation wrong. Your goal should not be to maximize the number of price, or to maximize anything. You are trying to minimize the total cost (so Math.max is out of place here). Also you will need to pass in something that describes both the cost and the length of each tile; your code doesn't show anything about that.

Finally, don't write code now. Just figure out the ideas. Write down a recurrence relation, and try to check whether it is correct. Then, write pseudocode and show it is correct. Only then should you write code. Diving straight into code is a mistake and is getting you mixed up in implementation details before you've even worked out the conceptual material. Also, on this site, you should not be showing us code: you should be showing us algorithms and pseudocode. This site is about algorithms, not code (StackOverflow is the place for code).

These hints should be enough to enable you to find a solution via dynamic programming (i.e., an efficient algorithm that always finds the least-cost tiling, with reasonable running time).