1、實驗五箱子裝載問題一、實驗目的二、實驗內容及要求1、使用貪心算法、回溯法、分支限界法解決箱子裝載問題。(任選兩種)2、通過上機實驗進行算法實現。3、保存和打印出程序的運行結果，并結合程序進行分析，上交實驗報告。三、實驗原理 回溯法原理:從開始結點出發，以深度優先方式搜索整個解空間。這個節點成為活結點，同時也成為 當前的擴展節點。在當前的擴展節點處，搜索向縱深方向一致一個新節點。貪心算法原理:貪心算法通過一系列的選擇來得到問題的解。他所做的每一個選擇都是當前狀態下局部 最好選擇，即貪心選擇。四、程序代碼(1)貪心算法#include #inelude void swap( int &x, int

2、 &y) /交換int t;t = x;X = y;y = t;void sort( int w, int t, int n) /排序，有小到大1、 理解和復習所學各種算法的概念;2、 掌握和復習所學各種算法的基本要素;3、 掌握各種算法的優點和區別;4、 通過應用范例掌握選擇最佳算法的設計技巧與策略;xtj = 1;_ c -= wtj;Lint mian()int n, c;printf( “請輸入物品個數：“)； scanf( %d, &n);printf( “請輸入最大容量：“)；scanf( %d, &c);int x200;/存儲物品編號int w200;/存儲每個物品重量for

3、( int i = 0; in; i+)printf(請輸入第d個物品重量：“，i); seanf( %d,&wi);int *t = new int n;/物品是否裝入for ( int j = 0; jn; j+)xj = 0;/初始化物品均未裝入loadi ng(x, w, c, n, t);printf(裝入物品編號為：“)；for ( int m = 0; m0)lastExcha ngeln dex = 0;for (j = 0; ji; j+)if ( wj + 1wj)swap (wj + 1,wj);lastExcha ngeln dex = j;swap (tj, tj +

4、 1);/物品的重量交換Li = lastExcha ngeln dex;t_void loading( int x, int噸，int c, int n, int * t) /最有裝載sort( w t, n); for (inti = 0; ixi = 0;n; i+)for (int j = 0; jn& t j = c; j+)/裝入for ( int k = 0; kn; k+)if (xk = 1)printf( %d “，tk);return 0;(2)回溯法#inelude #inelude #defi ne numlOOint bestx num = 0 ;/存放最優解int

5、 w num;集裝箱重量int x num; 解int bestw=0;/最優裝船重量int ew = 0);/當前已裝船重量int n;/集裝箱個數int e1;/第一船的重量int e2;/第二船的重量/限界函數遞歸求解void load in gRee( intint i;if (cwbestw)bestw = ew;for (i = 1; i = n; i+)bestxi = xi;return ;else if (ew + w t e1)/左分支滿足約束條件丄xt = 1;int rw = 0;for ( int i = t + rw = rw + wi;return (rw + e

6、w);1; t n)/到底葉子節點，求得一個可行解/當前解比以前解更優cw = cw + w t;loadingRec( t + 7);/前進繼續搜索下一節點/回溯；回復cw與xt的值cw = cw - w t;xt = 0;亍if (bound( t )bestw)/右分支滿足限界條件loadingRec( t + 1);int main()n = 4;/集裝箱個數w1 = 4, w2 = 5, w3 = 3, w4 = 2; c1 = 8;/第一個船重量/集裝箱重量c2 = 7; cw= 0;bestw = 0;/第二個船重量/從第一個集裝箱開始裝箱loadi ngRec(1);print

7、f(“第一船的最優裝載量為:%dn, bestw);printf(“第一船的最優解為“)；for ( int i = 1; i = n; i+)printf( %d , bestxi);/求剩余集裝箱的重量int cw2 = 0;for (int i = 0; i c2)pri ntf(無法將剩余集裝箱轉入第二船，問題無解elsep ri ntf(可以將剩余集裝箱裝入第二船，問題有解getchar();五、結果運行與分析(1)貪心算法 曲？乩冋口說nriDalaRMEing菟F r&.OHniplc5rxp4.1 -wc諸怖扎物品 15請輸入用大客旦：20請輸入第。牛物品蟲鼠肩輸扎帶 2 牛物品甫& 清輸扎第 St拘品甫堡 L青輸入第斗牛物品也拭););貪心算法并沒有求得最優解。(2)回溯法一弱的最憂裝占