箱子裝載問題

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

2、。他所做的每一個(gè)選擇都是當(dāng)前狀態(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+)/為每個(gè)物品編序號(hào) 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("請(qǐng)輸入物品個(gè)數(shù)：");scanf("%d", &n);printf("請(qǐng)輸入最大容量：");scanf("%d", &c);int x200;/存儲(chǔ)物品編號(hào) int w200;/存儲(chǔ)每個(gè)物品重量for (int i = 0; i<n; i+)printf("請(qǐng)輸入第%d個(gè)物品重量：", 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("裝入物品編號(hào)為：");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;/當(dāng)前已裝船重量int n;/集裝箱個(gè)數(shù)int c1;/第一船的重量int c2;/其次船的重量/限界函數(shù) int bound(int t)/ 選擇當(dāng)前節(jié)點(diǎn)又分支的剩余集裝箱重之和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é)點(diǎn)，求得一個(gè)可行解if (cw>bestw)/當(dāng)前解比以前解更優(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);/前進(jìn)連續(xù)搜尋下一節(jié)點(diǎn)/回溯；回復(fù)cw與xt的值cw = cw - wt;xt = 0;if (bound(t)>bestw)/右分支滿足限界條件loadingRec(t + 1);int main()n = 4;/集裝箱個(gè)數(shù)w1 = 4, w2 = 5, w3 = 3, w4 = 2;/集裝箱重量c1 = 8;/第一個(gè)船重量c2 = 7;/其次個(gè)船重量cw = 0;bestw = 0;loadi

8、ngRec(1);/從第一個(gè)集裝箱開頭裝箱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("可以將剩余集裝箱裝入其次船，問題