箱子装载问题

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

2、。他所做的每一个选择都是当前状态下局部最好选择，即贪心选择。四、程序代码（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("请输入物品个数：");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 ;/存放最优解int wnum;/集装箱重量int xnum;/解int bestw = 0

6、;/最优装船重量int cw = 0;/当前已装船重量int n;/集装箱个数int c1;/第一船的重量int c2;/其次船的重量/限界函数 int bound(int t)/ 选择当前节点又分支的剩余集装箱重之和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)/到底叶子节点，求得一个可行解if (cw>bestw)/当前解比以前解更优 bestw = cw;for (i = 1; i <

7、= n; i+)bestxi = xi;return;elseif (cw + wt<c1)/左分支满足约束条件xt = 1;cw = cw + wt;loadingRec(t + 1);/前进连续搜寻下一节点/回溯；回复cw与xt的值cw = cw - wt;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

8、ngRec(1);/从第一个集装箱开头装箱printf("第一船的最优装载量为：%dn", bestw);printf("第一船的最优解为");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("无法将剩余集装箱转入其次船，问题无解");elseprintf("可以将剩余集装箱装入其次船，问题