箱子裝載問題特選材料

1、實(shí)驗(yàn)五 箱子裝載問題一、實(shí)驗(yàn)?zāi)康?、 理解和復(fù)習(xí)所學(xué)各種算法的概念；2、 掌握和復(fù)習(xí)所學(xué)各種算法的基本要素；3、 掌握各種算法的優(yōu)點(diǎn)和區(qū)別；4、 通過應(yīng)用范例掌握選擇最佳算法的設(shè)計(jì)技巧與策略；二、實(shí)驗(yàn)內(nèi)容及要求1、使用貪心算法、回溯法、分支限界法解決箱子裝載問題。（任選兩種）2、通過上機(jī)實(shí)驗(yàn)進(jìn)行算法實(shí)現(xiàn)。 3、保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析，上交實(shí)驗(yàn)報(bào)告。三、實(shí)驗(yàn)原理回溯法原理：從開始結(jié)點(diǎn)出發(fā)，以深度優(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#includevoid 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; m0)lastexchangeindex = 0;for (j = 0; ji; j+)if (wj + 1wj)swap(wj + 1, wj);/物品的重量交換lastexchangeindex = j;swap(tj, tj + 1);i = lastexchange

3、index;void loading(int x, int w, int c, int n, int *t)/最有裝載sort(w, t, n);for (int i = 0; in; i+)xi = 0;for (int j = 0; jn&wtj = c; j+)xtj = 1;c -= wtj;/裝入 int mian()int n, c;printf(請輸入物品個(gè)數(shù)：);scanf(%d, &n);printf(請輸入最大容量：);scanf(%d, &c);int x200;/存儲(chǔ)物品編號(hào) int w200;/存儲(chǔ)每個(gè)物品重量for (int i = 0; in; i+)printf

4、(請輸入第%d個(gè)物品重量：, i);scanf(%d, &wi);int *t = new intn;/物品是否裝入for (int j = 0; jn; j+)xj = 0;/初始化物品均未裝入loading(x, w, c, n, t);printf(裝入物品編號(hào)為：);for (int k = 0; kn; k+)if (xk = 1)printf(%d , tk);return 0;（2）回溯法#include#include#define num 100int bestxnum = 0 ;/存放最優(yōu)解int wnum;/集裝箱重量int xnum;/解int bestw = 0;/最

5、優(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; tn)/到底葉子節(jié)點(diǎn)，求得一個(gè)可行解if (cwbestw)/當(dāng)前解比以前解更優(yōu) bestw = cw;for (i = 1; i = n; i+)bestxi = xi;return;elseif (cw + wtbestw)/右分支滿足限界條件loadingrec(t + 1);int main()n = 4;/集裝箱個(gè)

6、數(shù)w1 = 4, w2 = 5, w3 = 3, w4 = 2;/集裝箱重量c1 = 8;/第一個(gè)船重量c2 = 7;/第二個(gè)船重量cw = 0;bestw = 0;loadingrec(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 c2)printf(無法將剩余集裝箱轉(zhuǎn)入第二船，問題無解);elseprintf(可以將剩余集裝箱裝入第二船，問題有解);getchar();五、結(jié)果運(yùn)行與分析（1）貪心