OiO.lk Community platform!

Oio.lk is an excellent forum for developers, providing a wide range of resources, discussions, and support for those in the developer community. Join oio.lk today to connect with like-minded professionals, share insights, and stay updated on the latest trends and technologies in the development field.
  You need to log in or register to access the solved answers to this problem.
  • You have reached the maximum number of guest views allowed
  • Please register below to remove this limitation

Asteroid Mining - Dynamic Programming problem

  • Thread starter Thread starter PK96
  • Start date Start date
P

PK96

Guest
I was given the following assignment:

There is n gram of mineral to be dug up on a certain asteroid. At the beginning there is only one robot at our disposal. Each robot can do one of two activities in a day (which take up the whole day):

  1. dig up 1 gram of mineral
  2. clone itself (the clone can only take action the next day)

The task was to write a function that returned the minimum number of days needed to dig up at least n grams of mineral

Of course, I immediately realised that this was a dynamic programming problem, but I have no idea how to solve the problem this way.

The only thing I managed to do was the naive recursive solution, which doesn't pass all the tests, which doesn't surprise me, because n can be up to a million:

Code:
def mining_rec(n, r = 1, d = 0):
    if n <= 0:
        return d
    if r >= n:
        return d + 1

    if r == 1:
        return min(mining_rec(n - 1, r, d + 1), mining_rec(n, r + 1, d + 1))
    else:
        for i in range(r + 1):
            mining_robots = i
            cloning_robots = r - i
            return mining_rec(n - mining_robots, r + cloning_robots, d + 1)

Do you have any ideas on how this could be done using dynamic programming?
<p>I was given the following assignment:</p>
<p>There is <code>n</code> gram of mineral to be dug up on a certain asteroid. At the beginning there is only one robot at our disposal. Each robot can do one of two activities in a day (which take up the whole day):</p>
<ol>
<li>dig up 1 gram of mineral</li>
<li>clone itself (the clone can only take action the next day)</li>
</ol>
<p>The task was to write a function that returned the minimum number of days needed to dig up at least <code>n</code> grams of mineral</p>
<p>Of course, I immediately realised that this was a dynamic programming problem, but I have no idea how to solve the problem this way.</p>
<p>The only thing I managed to do was the naive recursive solution, which doesn't pass all the tests, which doesn't surprise me, because <code>n</code> can be up to a million:</p>
<pre class="lang-py prettyprint-override"><code>def mining_rec(n, r = 1, d = 0):
if n <= 0:
return d
if r >= n:
return d + 1

if r == 1:
return min(mining_rec(n - 1, r, d + 1), mining_rec(n, r + 1, d + 1))
else:
for i in range(r + 1):
mining_robots = i
cloning_robots = r - i
return mining_rec(n - mining_robots, r + cloning_robots, d + 1)

</code></pre>
<p>Do you have any ideas on how this could be done using dynamic programming?</p>
 

Latest posts

S
Replies
0
Views
1
Souvik Manna
S
S
Replies
0
Views
1
Shelling ford
S
Top