搬寝室.pptVIP

Dynamic Programming ---moving into a new dormitory Problem Question Can you find the optimal solution to the lowest sense of tiring to help the poor Mary? n is the total number of her baggage 2*k is the number of baggage she will move. (2=2*k=n2000) w[i] is the weight of the No.i baggage; dp[i][j] is the lowest sense of tiring when moving 2*i pieces of baggage from j pieces of baggage.  DP Step 1: characterizing the optimal sub-structure Moving into a new dormitory problem has the optimal sub-structure. The optimal solution for the lowest sense of tiring is dp[k][n] If we move the No.n b