装载问题 问题描述： 给定n个集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。集装箱装载问题要求确定在不超过轮船载重量的前提下，将尽可能多的集装箱装上轮船（贪心算法中的装载问题讨论的是装载件数；本题讨论的是最大装载重量。）
问题分析： 由于集装箱问题是从n个集装箱里选择一部分集装箱，假设解向量为X(x1, x2, …, xn)，其中xi∈{0, 1}， xi =1表示集装箱i装上轮船， xi =0表示集装箱i不装上轮船。 输入 每组测试数据：第1行有2个整数c和n。C是轮船的载重量（0＜c＜30000），n是集装箱的个数（n≤20）。第2行有n个整数w1, w2, …, wn，分别表示n个集装箱的重量。 输出 对每个测试例，输出两行：第1行是装载到轮船的最大载重量，第2行是集装箱的编号。
/装载问题回溯法实现 #include<iostream> using namespace std; #define NUM 100 int n; //集装箱的数量 int c; //轮船的载重量 int w[NUM]; //集装箱的重量数组 int x[NUM]; //当前搜索的解向量 int r; //剩余集装箱的重量 int cw; //当前轮船的载重量 int bestw; //当前最优载重量 int bestx[NUM]; //当前最优解 void backtrack(int t) { //到达叶子节点 if (t > n) { if (cw > bestw) { for (int i = 1; i <= n; i++) bestx[i] = x[i]; bestw = cw; } } //更新剩余集装箱的重量 r -= w[t]; //（1） //搜索左子树 if (cw + w[t] <= c) { x[t] = 1; cw += w[t]; //（2） backtrack(t + 1); cw -= w[t]; //（2） } //搜索右子树 if (cw + r > bestw) { x[t] = 0; backtrack(t + 1); } r += w[t]; //（1）恢复状态 } int main() { cout << "please input n,c:" << endl; cin >> c >> n; cout << "please input w[]: " << endl; for (int i = 1; i <= n; i++) { cin >> w[i]; } r = 0; for (int i = 1; i <= n; i++) { r += w[i]; } backtrack(1); cout << "the bestw is:" << bestw << endl; for (int i = 1; i <= n; i++) { if (x[i] != 0) cout << i << " "; } cout << endl; }