動态規劃(dp)算法總結

       動态規劃程式設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊算法。不象搜尋或數值計算那樣，具有一個标準的數學表達式和明确清晰的解題方法。動态規劃程式設計往往是針對一種最優化問題，由于各種問題的性質不同，确定最優解的條件也互不相同，因而動态規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動态規劃算法，可以解決各類最優化問題。是以讀者在學習時，除了要對基本概念和方法正确了解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創造性的技巧去求解。我們也可以通過對若幹有代表性的問題的動态規劃算法進行分析、讨論，逐漸學會并掌握這一設計方法。

      是以dp算法的難點在于找狀态轉移方程。在poj做了一些動态規劃的題目，在這裡做個總結。

1、poj 1160

a 題目描述：

 在v個村莊(村莊呈直線分布)設定p個郵局，使各個村莊到郵局的 總距離最短。

b 解題方案：

 cost[v][p]  代表在v個村莊建立p個郵局的最短距離

 dis[v][v]   ；dis[i][j] 表示在第i個村莊和第j個村莊之間建立一個郵局，顯然，這個郵局應該建在i和j的中間。

c 狀态轉移方程：

 cost[v][p] = cost[i][p-1] + dis[i+1][v] // p<=i<=v;

2、poj 1260

a 問題描述：

 有c個種類的珠寶，每個種類的珠寶有需要購買的個數n和相應的價值p，需要購買某一種需要花費(n+10)*p; 購買時，低品質的珠寶可以用高品質的珠寶代替；為了最終花費的錢最少。

 dp[c];dp[i]表示到第i中珠寶時花費的最少錢

 num[c];num[i]表示從0到i之間品質的珠寶的所有數目

 dp[i] = (num[i] + 10)*p[i]

 dp[i] = min(dp[i],dp[j]+(num[i] - num[j] + 10)*p[i]) // 0<=j<i

3、poj 1276

 有n中錢币，每種有ai張，價值di；要求湊出m價值，求湊出的最接近m的值。

b 解決方法：

 這是個多重背包問題，可以将重複價值的紙币加起來，或者直接當成一個個體。這樣就變成01背包了。

 for (i = 1; i<=count; i++) //count為有多少張錢币，v[i]對應第i張錢币的價值

       for (k = m; k>=v[i]; k--) // m 為最終要拼出的價值

          opt[k] = opt[k] | opt[k - v[i]]; //如果能拼出k，則opt[k]=1;

4、poj 1745

a 問題描述

 給出一列數，可以在相鄰兩個數之間執行相加或者相減的操作，得出的所有結果中是否能被k整除。

b 解決方法

 c[10001][101]; c[i][j]表示i個數字的運算結果sum, sum % k = j，若存在則為1，否則為0

c 狀态轉移方程

 c[i][j] = c[i-1][(j-a[i])%k] | c[i-1][(j+a[i])%k]; //這裡需要防止 j-a[i] 和 j+a[i]為負數，是以還需做一些操作,為了簡便，這裡就不寫了

5、poj 1837

 天平平衡問題，有g砝碼，每個砝碼重量為g[i],需要将這n個砝碼挂在天平c個刻度上(c[i]表示刻度達标),要求天平最終要平衡。天平左邊的刻度用負數表示，右邊的刻度用正數表示。求平衡的方法有幾種。

 因為有負數存在，是以需要做偏移，最大偏移量為 ：m = 砝碼的最大重量*最大尺度*砝碼的最大個數。

 w[i][j] //表示挂上第i個砝碼後，力矩為j的幾種方法

c 狀态轉移

 for(i=1;i<=g;i++) //g個砝碼

      for(j=1;j<=c;j++)//c個刻度

         for(k=0;k<7501;k++) //力矩

         {

                w[i][k+g[i]*c[j]] += w[i-1][k]; //将第i個砝碼挂在第j個刻度上，力矩的變化

         }

 cout<<w[g][3500]<<endl;