先看下題目：

已知14個西瓜 的重量，分別為： 23 21 12 19 18 25 20 22 16 19 12 15 17 14 請將這些瓜分成兩堆，每堆的個數不限，使兩堆西瓜重量之差最小。

我們知道，動態規劃類問題是存在明確的步驟的：

1. 分階段。

2. 狀態遷移方程。

3. 求最優解。

這道題要把西瓜分成兩堆，假設A堆和B堆，對于每個西瓜而言，要么分到A，要么分到B，和01背包有點像，要么裝包要么不裝包。既然和01背包問題類似，這道題就簡單了。01背包存在一個約束條件，就是背包的載重量有限制。對于每個物品而言，是否裝包需要和背包剩余載重量比較。那么對于西瓜分堆問題呢？什么情況下分到A組？什么情況下不分到A組？題目要求兩堆西瓜重量之差最小，假設變量 avg 為西瓜總重量的一半，A堆重量不大于B堆，那么問題就變成了在不超過A堆重量上限情況下，怎么樣分配西瓜使得A堆值最大，這樣思考就和01背包問題一樣了。假設西瓜從1到n編號，變量m[i][j]表示A堆容量j，可取西瓜范圍為1,2..i的最大重量。當j < wi的時候，放不下i，這時候m[i][j] = m[i-1][j]；當j >= wi的時候，需要比較放瓜和不放瓜A堆的最大重量值，即比較

m[i-1][j-wi]+wi 和m[i-1][j]的大小。通過遞推我們可以求得最優解m[13][avg]；在求取最優解序列的時候，和01背包一樣。

這道題的難點可能在于想到A堆的約束條件，即avg，這個則需要多多思考和練習了。

下面是本題的c代碼實現：

/** 西瓜分堆問題**/#include <stdio.h>#define MAX(a, b) ((a) > (b) ? (a) : (b))void main() {int i,j,n, k, w[30] = {0}, m[30][1000] = {0};int c[30] = {0}; printf("輸入西瓜個數："); scanf("%d", &n);if (n > 30) n = 30;k = 0;for (i = 0; i < n; i++){printf("輸入第%d個瓜的重量：", i + 1);scanf("%d", &w[i]);k += w[i];}//得到平均重量k = k / 2;printf("k = %d\n", k);//初始化邊界for (j = 0; j <= k; j++){if (j >= w[0])m[0][j] = w[0];elsem[0][j] = 0;}//狀態遞推for (i = 1; i < n; i++){for (j = 0; j <= k; j++){if (j >= w[i])m[i][j] = MAX(m[i-1][j], m[i-1][j-w[i]] + w[i]);elsem[i][j] = m[i-1][j];}}//打印最優解for (j = k, i = n - 1; i >= 1; i--){if (j >= w[i]){if (m[i][j] == m[i-1][j])c[i] = 2; //B堆else{c[i] = 1; //A堆j -= w[i];} }elsec[i] = 2; }if (j >= w[0])c[0] = 1;printf("A堆的瓜：");for (j = 0, i = 0; i < n; i++){if (c[i] == 1){printf("%d ", w[i]);j += w[i];}}printf(" 總和：%d \nB堆的瓜：", j);for (k = 0, i = 0; i < n; i++){if (c[i] == 2){printf("%d ", w[i]);k += w[i];}}printf(" 總和：%d \n 兩堆瓜的重量差為：%d\n",k, ((k > j) ? (k - j) : (j - k)));return; }

參考資料：

1.?數據結構?: C語言版/ 嚴蔚敏，吳偉民編著

=============================================================================================

Linux應用程序、內核、驅動開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結

以上是生活随笔為你收集整理的动态规划 dp01 西瓜分堆问题 c代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。