Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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