0
$\begingroup$

Ok so we have lets say 2 big wooden stakes, each has a length of $2$ $meters$. Our goal is to create as many photo frames as possible.

Each photo frame is consisted of $2\times50cm$ pieces and $2\times30cm$ pieces.

I want to create a dynamic programming recursion formula but i cannot properly conduct it. What i think for the problem is this:

We start off in stage $(200,200)$ and we can create a frame in multiple ways such as : $(100,60)$ or $(150,90)$ or $(40,200)$ and so on. But how can i convert this into a recursion formula??

$\endgroup$
  • $\begingroup$ What do you need a recursion for? you have 400 cm of wood. Each frame requires a minimum of 160 cm of wood. You can only get two frames out of that, no matter how you cut them up. $\endgroup$ – Paul Sinclair Jun 14 '18 at 23:39
  • $\begingroup$ i know the problem is trivial. but i want to find the recursion formula for it , so when i have to deal with a more complex problem i will know what to do $\endgroup$ – Mario Zelic Jun 15 '18 at 8:12
1
$\begingroup$

This doesn't directly answer your "recursion" question. I am not exactly sure what you even mean by that. But it does address one way of approaching problems like this, so maybe it will be helpful.

If you want to generalize your approach to problem-solving, then you need to think about more generalized problems. you don't have $2$ stakes - you have $n$ stakes. You could also generalize the length of the stakes and of the frame pieces, but for various reasons, I think in this case it will be more helpful to only generalize one element first.

The next thing you want to do, and I cannot emphasize this enough - it is a major stumbling block for students and even rocket scientists - always immediately convert measurements to all be in consistent units. You have stakes of length $200$ cm.

To maximize the number of frames you can get, you need to minimize the wastage for each stake. For this, you do not look at how you can get two $50$ cm frames and two $30$ cm frames. Instead, you look at the various ways a stake can be divided up into 50 and 30 cm lengths:

  • $4 \times 50 + 0 \times 30$ cm with no scrap
  • $3 \times 50 + 1 \times 30$ cm with $20$ cm scrap
  • $2 \times 50 + 3 \times 30$ cm with $10$ cm scrap
  • $1 \times 50 + 5 \times 30$ cm with no scrap
  • $0 \times 50 + 6 \times 30$ cm with $20$ cm scrap

If we divide $j$ stakes into four $50$ cm strips and $2k$ stakes into one $50$ cm strip and five $30$ cm strips ($2k$ because we need an even number of each strip), then we get $(4j+2k) 50$ cm strips and $(10j)30$ cm strips. To have no waste, we need these counts to be the same: $$4j + 2k = 10j\\k = 3j$$ whose smallest solution is $j = 1, k = 3$. So given $2k +j = 7$ stakes, we can divide them up completely into ten $50$ cm strips and ten $30$ cm strips, making 5 frames.

If $n = 7q + r$ for $0 \le r \le 6$, then you can divide $7q$ stakes perfectly to get $5q$ frames. All that remains is how to divide up the remaining $r$ stakes. The first 4 cases are trivial. We can make 1 frame each from the $r$ stakes:

  • $r = 0: 0$ additional frames, no waste.
  • $r = 1: 1$ additional frame, $40$ cm wasted.
  • $r = 2: 2$ additional frames, $80$ cm wasted.
  • $r = 3: 3$ additional frames, $120$ cm wasted.

With $r = 4$, you have $800$ cm of stakes, which is enough length for $5$ frames. But this would require no wastage, and we already have seen that it takes $7$ stakes to accomplish that. So we still have the pattern

  • $r = 4: 4$ additional frames, $160$ cm wasted.

For $r = 5$, we can divide the stakes by $$ 2 (3 \times 50 + 1 \times 30)\\2(1 \times 50 + 5 \times 30)\\1(4 \times 50 + 0 \times 30)$$ which gives

  • $r = 5: 6$ additional frames, $40$ cm wasted.
  • $r = 6: 7$ additional frames, $80$ cm wasted.

So the maximum number of frames that can be made from $n = 7q + r$ stakes is $5q + r$ when $r \le 4$ and $5q + r + 1$ when $r =5$ or $r = 6$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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