There are $n$ houses numbered $\{1, 2, 3, \dots, n\}$. The cost of laying a cable that serves houses $j, j+1, j+2, \dots, j+k $ is $f (j, k)$. One cable can serve a maximum of 10 houses. The optimal cost of serving houses $\{i, i+1, i+2, \dots, n\}$ is $V_i$. Write down $V_i$ in terms of $V_{i+1}$ such that it can be evaluated.

The expression that I obtained is $$V_i=\text {Min}\{f (i, i)+V_{i+1}, f (i, i+1)+V_{i+2}, \dots, f (i, i+9)+V_{i+10}\} $$

Is it correct? I'm not so sure it leads to a simplification completely in terms of $V_{i+1} $ though.

  • $\begingroup$ @Cristopher- Why do you think I misread it? $\endgroup$ – fierydemon Jun 20 '15 at 3:11

Your Answer

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

Browse other questions tagged or ask your own question.