装载问题-回溯法

有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");
}

等价于先序遍历，先找左子树，然后再进行右子树。