搬寝室.ppt

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 baggage,the lowest sense of tiring dp[k-1][n-2] should also be optimal; or else we can replace the non-optimal solution with an optimal one If we don’t move the No.n baggage,the lowest sense of tiring dp[k][n-1](= dp[k][n] )should also be optimal; or else we can replace this non-optimal solution with an optimal one DP Step 2: construct the recursion solution Case 1: We do not move No.j baggage. – We select best 2*i pieces from { 1, 2, …, j-1 } Case 2: We move No.j baggage. –If we move j ,we must move j-1,as we should move a pair of baggage. – We select best 2*(i-1) pieces from { 1, 2, …, j-2 }  Assuming k=1 when n=2,there is only one choice,that is,moving w[1] and w[2] together.So dp[1][2]=(w[1]-w[2])^2. when n=3,there are two choices,that is,w[1],w[2]or w[2],w[3].So dp[1][3]=min{dp[1][2],dp[0][1]+(w[2]-w[3])^2} Assuming k=2 when n=4,there is only one choice,that is ,moving w[1], w[2] together and moving w[3],w[4] together.So dp[2][4]=(w[1]-w[2])^2+(w[3]-w[4])^2. when n=5,dp[2][5]=min{dp[2][4],dp[1][3]+(w[4]-w[5])^2}. …… Code  input k,n, w[1],….w[n]; Make an array dp[0][0],….,dp[k][n] ; for i=0 to n dp[0][i]=0;     sort(w);                 for i=1 to k         {               dp[i][i+i]=dp[i-1][i+i-2]+(w[i+i-1]-w[i+i])*(w[i+i-1]-w[i+i]);               for j=2*i+1 to n                 dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+(w[j]-w[j-1])*(w[j]-w[j-1