箱子装载问题[特选材料]

1、实验五 箱子装载问题一、实验目的1、 理解和复习所学各种算法的概念；2、 掌握和复习所学各种算法的基本要素；3、 掌握各种算法的优点和区别；4、 通过应用范例掌握选择最佳算法的设计技巧与策略；二、实验内容及要求1、使用贪心算法、回溯法、分支限界法解决箱子装载问题。（任选两种）2、通过上机实验进行算法实现。 3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。三、实验原理回溯法原理：从开始结点出发，以深度优先方式搜索整个解空间。这个节点成为活结点，同时也成为当前的扩展节点。在当前的扩展节点处，搜索向纵深方向一致一个新节点。贪心算法原理：贪心算法通过一系列的选择来得到问题的解。他所做

2、的每一个选择都是当前状态下局部最好选择，即贪心选择。四、程序代码（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(请输入物品个数：);scanf(%d, &n);printf(请输入最大容量：);scanf(%d, &c);int x200;/存储物品编号 int w200;/存储每个物品重量for (int i = 0; in; i+)printf

4、(请输入第%d个物品重量：, i);scanf(%d, &wi);int *t = new intn;/物品是否装入for (int j = 0; jn; j+)xj = 0;/初始化物品均未装入loading(x, w, c, n, t);printf(装入物品编号为：);for (int k = 0; kn; k+)if (xk = 1)printf(%d , tk);return 0;（2）回溯法#include#include#define num 100int bestxnum = 0 ;/存放最优解int wnum;/集装箱重量int xnum;/解int bestw = 0;/最

5、优装船重量int cw = 0;/当前已装船重量int n;/集装箱个数int c1;/第一船的重量int c2;/第二船的重量/限界函数 int bound(int t)/ 选择当前节点又分支的剩余集装箱重之和int rw = 0;for (int i = t + 1; tn)/到底叶子节点，求得一个可行解if (cwbestw)/当前解比以前解更优 bestw = cw;for (i = 1; i = n; i+)bestxi = xi;return;elseif (cw + wtbestw)/右分支满足限界条件loadingRec(t + 1);int main()n = 4;/集装箱个

6、数w1 = 4, w2 = 5, w3 = 3, w4 = 2;/集装箱重量c1 = 8;/第一个船重量c2 = 7;/第二个船重量cw = 0;bestw = 0;loadingRec(1);/从第一个集装箱开始装箱printf(第一船的最优装载量为：%dn, bestw);printf(第一船的最优解为);for (int i = 1; i = n; i+)printf(%d , bestxi);/求剩余集装箱的重量int cw2 = 0;for (int i = 0; i c2)printf(无法将剩余集装箱转入第二船，问题无解);elseprintf(可以将剩余集装箱装入第二船，问题有解);getchar();五、结果运行与分析（1）贪心