箱子裝載問題

1、精選文檔試驗五 箱子裝載問題一、試驗目的1、 理解和復習所學各種算法的概念；2、 把握和復習所學各種算法的基本要素；3、 把握各種算法的優(yōu)點和區(qū)分；4、 通過應用范例把握選擇最佳算法的設計技巧與策略；二、試驗內(nèi)容及要求1、使用貪心算法、回溯法、分支限界法解決箱子裝載問題。（任選兩種）2、通過上機試驗進行算法實現(xiàn)。 3、保存和打印出程序的運行結(jié)果，并結(jié)合程序進行分析，上交試驗報告。三、試驗原理回溯法原理：從開頭結(jié)點動身，以深度優(yōu)先方式搜尋整個解空間。這個節(jié)點成為活結(jié)點，同時也成為當前的擴展節(jié)點。在當前的擴展節(jié)點處，搜尋向縱深方向全都一個新節(jié)點。貪心算法原理：貪心算法通過一系列的選擇來得到問題的解

2、。他所做的每一個選擇都是當前狀態(tài)下局部最好選擇，即貪心選擇。四、程序代碼（1）貪心算法#include<stdio.h>#include<stdlib.h>void swap(int &x, int &y)/交換 int t;t = x;x = y;y = t;void sort(int w, int t, int n)/排序，有小到大 for (int m = 0; m<n; m+)/為每個物品編序號 tm = m;int i, j;int lastExchangeIndex;i = n - 1;while (i>0)lastExchang

3、eIndex = 0;for (j = 0; j<i; j+)if (wj + 1<wj)swap(wj + 1, wj);/物品的重量交換lastExchangeIndex = j;swap(tj, tj + 1);i = lastExchangeIndex;void loading(int x, int w, int c, int n, int *t)/最有裝載sort(w, t, n);for (int i = 0; i<n; i+)xi = 0;for (int j = 0; j<n&&wtj <= c; j+)xtj = 1;c -= w

4、tj;/裝入 int mian()int n, c;printf("請輸入物品個數(shù)：");scanf("%d", &n);printf("請輸入最大容量：");scanf("%d", &c);int x200;/存儲物品編號 int w200;/存儲每個物品重量for (int i = 0; i<n; i+)printf("請輸入第%d個物品重量：", i);scanf("%d", &wi);int *t = new intn;/物品是否裝入fo

5、r (int j = 0; j<n; j+)xj = 0;/初始化物品均未裝入loading(x, w, c, n, t);printf("裝入物品編號為：");for (int k = 0; k<n; k+)if (xk = 1)printf("%d ", tk);return 0;（2）回溯法#include<stdio.h>#include<stdlib.h>#define num 100int bestxnum = 0 ;/存放最優(yōu)解int wnum;/集裝箱重量int xnum;/解int bestw = 0

6、;/最優(yōu)裝船重量int cw = 0;/當前已裝船重量int n;/集裝箱個數(shù)int c1;/第一船的重量int c2;/其次船的重量/限界函數(shù) int bound(int t)/ 選擇當前節(jié)點又分支的剩余集裝箱重之和int rw = 0;for (int i = t + 1; t<n; t+)rw = rw + wi;return (rw + cw);/上界 /遞歸求解void loadingRec(int t)int i;if (t>n)/到底葉子節(jié)點，求得一個可行解if (cw>bestw)/當前解比以前解更優(yōu) bestw = cw;for (i = 1; i <

7、= n; i+)bestxi = xi;return;elseif (cw + wt<c1)/左分支滿足約束條件xt = 1;cw = cw + wt;loadingRec(t + 1);/前進連續(xù)搜尋下一節(jié)點/回溯；回復cw與xt的值cw = cw - wt;xt = 0;if (bound(t)>bestw)/右分支滿足限界條件loadingRec(t + 1);int main()n = 4;/集裝箱個數(shù)w1 = 4, w2 = 5, w3 = 3, w4 = 2;/集裝箱重量c1 = 8;/第一個船重量c2 = 7;/其次個船重量cw = 0;bestw = 0;loadi

8、ngRec(1);/從第一個集裝箱開頭裝箱printf("第一船的最優(yōu)裝載量為：%dn", bestw);printf("第一船的最優(yōu)解為");for (int i = 1; i <= n; i+)printf("%d ", bestxi);/求剩余集裝箱的重量int cw2 = 0;for (int i = 0; i <= n; i+)if (bestxi = 0)cw2 += wi;if (cw2>c2)printf("無法將剩余集裝箱轉(zhuǎn)入其次船，問題無解");elseprintf("可以將剩余集裝箱裝入其次船，問題