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