本文目录 ⌄
有n个集装箱要装上2艘载重量分别为C1和C1的轮船。其中集装箱i的重量为Wi，且（W1+W2+….+Wn<=C1+C2）。
装载问题是，是否有一个合理装载方案，可将这n个集装箱都装上这2个轮船，若有，请给出解决方案。
例如
C1=C2=50, W=(10,40,40) 可以装载（10，40） （40）
C1=C2=55, W=(20,40,40) 无法装载
分析
装载问题很适合使用回溯法，当不符合条件时回退到上一个状态。
#include <iostream>
using namespace std;
/*
1.在递归前增加回退语句,如果不符合条件return;
2.像两艘船里装东西,先装第一条,遍历左子树
3.先序遍历
*/
int c1 = 50, c2 = 50, N = 3;
int a[10], w[3] = {10, 40, 40};
void dfs(int n) {
if (n == N ) {
int cur_c1 = 0, cur_c2 = 0;
for (int i = 0; i < N; i++) {
cur_c1 += (a[i] == 1) * w[i];
cur_c2 += (a[i] == 2) * w[i];
}
if (cur_c1 > c1 || cur_c2 > c2) return;
for (int i = 0; i < N; i++) { //1 2 表示船
cout << a[i]<<" ";
}
cout<<endl;
return;
}
for (int i = 1; i < 3; i++) {
a[n] = i;
dfs(n + 1); //先放左船,然后装入下一个货物
}
}
int main() {
dfs(0);
system("pause");
}
等价于先序遍历，先找左子树，然后再进行右子树。