interestingLSY 的博客

interestingLSY 的博客

草算纸

posted on 2018-07-14 12:26:46 | under 未分类 |

$$f_i = min\{f_j+Tran_{i,j}+Cost_i\}\qquad j \in [1,i-1]$$

.

$$Tran_{i,j} = \Sigma_{k=j+1}^{i-1}(dis_i-dis_k)*num_k$$

$$=dis_i*\Sigma_{k=j+1}^{i-1}num_k\ -\ \Sigma_{k=j+1}^{i-1}dis_k*num_k $$

.

$$sum_x = \Sigma_{i=1}^{x}num_i$$

$$g_x = \Sigma_{i=1}^{x}dis_i*num_i$$

$$\therefore Tran_{i,j} = dis_i*(sum_{i-1}-sum_{j})\ -\ (g_{i-1}-g_j)$$

.

$$\therefore f_i = min\{f_j+Tran_{i,j}+Cost_i\}\qquad j \in [1,i-1]$$

$$f_i = min\{f_j+dis_i*(sum_{i-1}-sum_{j})\ -\ (g_{i-1}-g_j)+Cost_i\}\qquad j \in [1,i-1]$$

$$= min\{f_j+dis_i*sum_{i-1}-dis_i*sum_{j}\ -\ g_{i-1}+g_j+Cost_i\}\qquad j \in [1,i-1]$$

$$= f_j-dis_i*sum_{j}+g_j+dis_i*sum_{i-1}-g_{i-1}+Cost_i\qquad j \in [1,i-1]$$

$$f_i+dis_i*sum_j = f_j+g_j$$

$$b\ \ \ \ +\ \ \ k\ \ *\ \ x \ \ \ =\ \ \ \ \ y$$