2
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ By "square tiles" you mean blocks of consecutive places? and why reducing to shortest path didn't work out? $\endgroup$
    – Parham
    Nov 19, 2013 at 18:03
  • $\begingroup$ Shortest path wouldn't let me re-use the same path over and over, when im allowed to reuse blocks. I don't know what you mean by "consecutive places", they are all square tiles of x unit length. $\endgroup$ Nov 19, 2013 at 18:05
  • $\begingroup$ I mean if the underlaying setting is just a line that you want to partition into certain blocks/segments then it's a 1D setting and square gives a 2D impression. It's just about the way you worded your problem. $\endgroup$
    – Parham
    Nov 19, 2013 at 18:19
  • $\begingroup$ This is a nice exercises problem with a beautiful solution. I don't want to steal the joy of discovering the solution for yourself. Dividing cost by length is a greedy algorithm. So, what other strategies do you know for constructing algorithms? (As a brainstorming aid, if you're stuck: You might take an algorithms textbook, go through the list of chapters, and for each chapter title, check whether you can see any way to apply that chapter's concept to your problem. I can pretty much guarantee the technique I'm thinking of will get an entire chapter in most algorithms textbooks.) $\endgroup$
    – D.W.
    Nov 19, 2013 at 19:11
  • $\begingroup$ @D.W. ah, one of the chapters is Divide and Conquer. I could use it to solve the smaller lengths and slowly move up from that until I've solved the question. I will try that $\endgroup$ Nov 19, 2013 at 19:51

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for this. It took me about 2 days of lots of whiteboard work and lots of failures, but I finally broke the sub-problems down correctly and isolated my problems. It really helped having the recurrence relationship down, as at that point it was just implementation that was needed. Thanks again! $\endgroup$ Nov 21, 2013 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.