C++——《算法分析》实验伍——箱子装载问题

实验目的：
1、理解和复习所学各种算法的概念；
2、 掌握和复习所学各种算法的基本要素；
3、 掌握各种算法的优点和区别；
4、 通过应用范例掌握选择最佳算法的设计技巧与策略；

实验原理
1、贪心算法首先排序集装箱，不断挑选相对重的加入数组
2、回溯法构建二叉树，通过判断建立左右子树并不断剪枝求得可行解并比较出最优解

实验内容：
1、使用贪心算法、回溯法、分支限界法解决箱子装载问题。（任选两种）
2、通过上机实验进行算法实现。
3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。

源程序：
回溯法：

#include <cstdio> #include <iostream> using namespace std; int n; //集装箱数 int cw; // 当前重量 int bestw; //最优重量 int c1; //第一艘轮船的载重量 int c2; //第二艘轮船的载重量 int x[100]; //解 int bestx[100]; //最优解 int w[100]; //重量void load(int t) {if (t > n){if (cw > bestw){bestw = cw;for (int i = 0; i < n; i++)bestx[i] = x[i];}return;}else {if (cw + w[t] <= c1) {cw += w[t];x[t] = 1;load(t + 1);x[t] = 0;cw -= w[t];}int rw = 0;for (int i = t + 1; t <= n; t++) rw += w[i];if ((rw + cw) > bestw) {load(t + 1);} } }int main() {cout << "回溯法：" << endl;cout << "第1船载重量为：";cin >> c1;cout << "第2船载重量为：";cin >> c2;cout << "集装箱个数为：";cin >> n;cout << "集装箱重量为："<<endl;for (int i = 0; i < n; i++) cin >> w[i];cw = 0;bestw = 0;load(1);cout << "第1船的最优载重量为：" << bestw << endl;cout << "第1船的最优解为：";for (int i = 0; i < n; i++) cout << bestx[i]<< " ";cout << endl;int cw2 = 0;for (int i = 0; i < n; i++) if (bestx[i] == 0) cw2 += w[i];if (cw2 > c2) cout << "无法将剩余集装箱装入第2船，问题无解"<<endl;else cout << "可以将剩余集装箱装入第2船，问题有解"<<endl; }

贪心算法：

#include <cstdio> #include <cstdlib> #include <iostream> using namespace std; int x[100], w[100],w1[100]; void swap(int& x, int& y) {int t;t = x;x = y;y = t; } void sort(int w[], int n) {int i, j;int last;i = n - 1;while (i > 0){last = 0;for (int j = 0; j < i; j++){if (w[j + 1] > w[j]){swap(w[j + 1], w[j]);last = j;}}i = last;} } void load(int x[], int w[], int c, int n) {sort(w, n);for (int i = 0; i < n; i++) x[i] = 0;for (int j = 0; j < n ; j++) {if (w[j] <= c) {x[j] = 1;c -= w[j];}} }int main() {int n, c1,c2;cout << "贪心算法：" << endl;cout << "第1船载重量为：";cin >> c1;cout << "第2船载重量为：";cin >> c2;cout << "集装箱个数为：";cin >> n;cout << "集装箱重量为：" << endl;for (int i = 0; i < n; i++){cin >> w[i]; w1[i] = w[i];}load(x, w, c1, n);int bestw = 0;for (int k = 0; k < n; k++) {if (x[k] == 1) bestw += w[k];}cout << "第1船的最优载重量为：" << bestw << endl;cout << "第1船的最优解为：";for (int i = 0; i < n; i++){int count = 0;for (int j = 0; j < n; j++){if ((w1[i] == w[j]) && (x[j] == 1) && count < 1){cout << "1 ";count++;}else if ((w1[i] == w[j]) && (x[j] == 0) && count < 1){cout << "0 ";count++;}}}cout << endl;int cw2 = 0;for (int i = 0; i < n; i++) if (x[i] == 0) cw2 += w[i];if (cw2 > c2) cout << "无法将剩余集装箱装入第2船，问题无解" << endl;else cout << "可以将剩余集装箱装入第2船，问题有解" << endl; return 0; }

实验结果：

总结

以上是生活随笔为你收集整理的C++——《算法分析》实验伍——箱子装载问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。