# Dynamic Programming Trouble, Optimizing time

A robot goes from terminal to terminal collecting bolts. The robot needs to collect at least $m$ bolts and there are $n$ terminals. Terminal $i$ gives the robot a certain number of bolts denoted by $b_i$, however the robot has to wait time $w_i$ at a terminal before the bolts are dispensed. The robot needs to collect the bolts in the minimum amount of big-$O$ time.

I'm having a great amount of difficulty figuring out what exactly it means to produce a dynamic programming solution to a simple problem like this.

Can anyone start me off in the right direction?

-
Have you heard of knapsack problem? – Aryabhata Apr 15 '13 at 6:15
No? Well, I guess I have now. – Randi Marsh Apr 15 '13 at 6:17
The knapsack problem doesn't appear to be related. Here we are trying to minimize time while satisfying the requirement of collecting $m$ bolts. – Randi Marsh Apr 15 '13 at 6:31
There is a dynamic programming algorithm for that, and it is quite similar. Perhaps it helps you. Good luck! – Aryabhata Apr 15 '13 at 6:37

Recurse Using:

Let the state of the system be the total number of bolts left to collect. $S_t$ is the total number of bolts left to collect at step $t$. $$V_t(S_t)=\min_{x\in \mathcal{A}(S_t)}\{ C_t(S_t,x_t)+V_{t+1}(S_{t+1})\}$$ Where:

$V_t$ - Waiting Time Spent Till Step $t$

$S_t$ - State at step t

Also, $$S_{t+1}=S_t-b_{x_t}$$

$C_t$ - Cost of step t = $w_{x_t}$

This should be good modeling start. You can then use Backwards Recursion for solving.

For more details, refer the book by Warren Powell. (I personally hate the book but it seems to be the only one that I can remember and it's not bad for modeling.)

-