简单装载问题(回溯法)

问题描述

有n个集装箱要装上一艘载重量为W的轮船,其中集装箱i ( 1≤i≤n )的重量为wi。不考虑集装箱的体积限制,现要这些集装箱中选出若干装上轮船, 使它们的重量之和等于W ,当总重量相同时要求选取的集装箱个数尽可能少。

• 左剪枝条件

  已选集装箱的重总量 + 当前要选择的集装箱重量 ≤ 目标总量

  • 左剪枝是选择当前集装箱

• 右剪枝条件

  已选集装箱的重总量 + (剩余集装箱重量 - 当前要选择的集装箱重量) ≥ 目标总量

  • 右剪枝是不选择当前集装箱。所以当排除当前集装箱, 剩下的集装箱加上已选集装箱的重量不足目标重量, 也就是说,即使把剩下的全部集装箱选上,都已经无法满足目标重量了，再继续搜索下去也没用了。所以直接回溯即可。

• 符合剪枝条件即可向下一层继续搜索，直达不符合剪枝条件或者到达叶子节点；不符合剪枝条件就需要回溯

• 递归出口

  当搜索到叶子节点，就代表得到解决方案了，此时结束函数调用。

static List<int> pathList = new List<int>();  //深度搜索路径

/// <summary>
/// 简单装载-回溯法
/// </summary>
/// <param name="w">集装箱列表</param>
/// <param name="tw">已选择的集装箱总重量</param>
/// <param name="rw">剩下的集装箱总重量</param>
/// <param name="d">递归深度</param>
static void dfs(int[] w, int tw, int rw, int d)
{
	if (d == w.Length)
	{
        //输出方案
		foreach (int item in pathList)
			Console.Write("{0} ", item);
		Console.Write("\n");
		return;
	}

	pathList.Add(1);
	if (tw + w[d] <= 10)  //左剪枝
	{
		dfs(w, tw + w[d], rw - w[d], d + 1);
	}
	pathList.RemoveAt(pathList.Count - 1);  //回溯

	pathList.Add(0);
	if(tw + rw - w[d] >= 10)  //右剪枝
	{
		dfs(w, tw, rw - w[d], d + 1);
	}
	pathList.RemoveAt(pathList.Count - 1);  //回溯
}