0-1背包问题(回溯算法)

关于0-1背包问题是回溯算法的一个经典例子就这个问题来记录一下自己对回溯算法的初步理解

因为自己对这个算法也只是入门阶段所以有什么不正确的地方欢迎大家指正

1.我个人理解(现目前阶段的理解)：回溯算法顾名思义就是不断往回算

举个例子：你要从A地点到B地点在这个过程中有有限个路口任你选择

1.我对你加了约束条件在从A到B的这个过程中你不能超过一个时间T 超过你就不能继续走这条路你就必须要返回到上一个路口重新选择另一个路口，当你发现你重新选择的路口还是不行那你就需要再返回到你上上个路口继续试探在这个过程中你是不是就在回溯了？再思考：我在不超过T中也有很多路径到达但是我又提出了一个要求我希望你能告诉我到达B的最少时间是多少那么就是一个最优解问题在这个过程中我们可以知道要使用回溯算法是有条件的他得有约束条件（不符合条件的我们就不尝试了这就是剪枝）也必须要有结束条件 ------解空间子集树

0-1背包问题

问题：给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

0-1背包问题(回溯算法)

我根据这张图来分析这个0-1背包问题：Y代表取想x[i]的物品 N代表不去（我在看了很多他们的解释自己又想了想我对 0-1背包问题可以看做是解空间树我是假设把x[i]看成是一个结点那么我们来看看如何来理解回溯算法）

a:假设我们第一件商品不取第二件商品也不取第三件商品也不取我们就来到了1处现在就得出一个价值（因为是第一个就假设他是最优价值）

b.现在我们就又回溯到第二件商品处换一个方向第三件商品我们取就到了2处又得出一个价值与最佳价值作比较（谁大谁留）

c.我们现在有回溯到第二件商品处我们第二件商品又要取那第三件商品可以取也可以不取又比较价值

d.我们又接着回溯到第一件商品处我们又开始进行第二件商品取/不取第三件商品取/不取

最后就回溯出了最佳价值基本的思想就是这样的但是在这中间需要加约束条件加以剪枝（不能超过背包重），这里就没有体现出来到了叶子节点就要出来啦。来看一下代码

package practice;

/**
 * 给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。 问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
 * 
 * @author fulisha
 *
 */
public class _05 {

	static int BestValue = 0; // 最优值；当前的最大价值，初始化为0
	static int[] BestX; // 最优解；BestX[i]=1代表物品i放入背包，0代表不放入
	//
	static int CurWeight = 0; // 当前放入背包的物品总重量
	static int CurValue = 0; // 当前放入背包的物品总价值
	static int N = 3;// 物品数量
	static int C = 16;// 物品的总容量
	static int W[] = { 10, 8, 5 }; // 每个物品的重量
	static int v[] = { 5, 4, 1 };// 每个物品的价值
	static int x[] = { 0, 0, 0 };// x[i]=1代表物品i放入背包，0代表不放入

	public static int backtrack(int t) {
		// 如果是子节点 当前价值和最佳价值做判断 保存最佳价值
		if (t > N - 1) {
			if (CurValue > BestValue) {
				BestValue = CurValue;
			}
			return BestValue;
		}
		// 如果不是子节点 对子节点进行遍历
		else {
			// 就两种情况 取或不取 用0/1表示
			for (int i = 0; i <= 1; i++) {
				x[t] = i;
				if (i == 0) {
					// 如果是不取 就不需要进行判断 直接到下一个节点
					backtrack(t + 1);
				} else
				// 放入背包就进行约束条件 判断放入背包的东西是否合法
				{
					if (CurWeight + W[t] <= C) {
						CurWeight += W[t];
						CurValue += v[t];
						// 当东西装进入背包后你可以进行对下个商品的判断了
						backtrack(t + 1);
						//能执行以下两个语句就说明你回溯到了上一个节点 所以你就需要恢复现场 把你刚刚拿的东西退出来 我们要冲上一个节点又要重新来遍历 如果不减你就会多加一遍 
						CurWeight -= W[t];
						CurValue -= v[t];
					}
				}
			}
		}
		return BestValue;
	}

	public static void main(String[] args) {
		backtrack(0);
		System.out.println(BestValue);
		for (int i = 0; i < 3; i++) {
			// System.out.println(BestX[i]);
		}
	}

}

0-1背包问题(回溯算法)

再加一个小例子：牌数问题

小明被劫持到X赌城，*与其他3人玩牌。一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。这时，小明脑子里突然冒出一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？

解释：这个也是利用递归加回溯约束条件就是每人必须拿到13张他和上面那一道题也有不一样的地方就是他不需要剪枝这就好比数学上的全排列把所有的情况都包括在这里面还包含了重复数

package practice;

/**
 * 小明被劫持到X赌城，*与其他3人玩牌。 一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。 这时，小明脑子里突然冒出一个问题：
 * 如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？
 * 
 * @author fulisha
 *
 */
public class _09 {
	static int sum;
	static int t;
	// sum:代表取牌总数 cur代表当前所拥有的牌的总数 t代表有多少种取法
	public static void DFS(int cur) {

		if (sum > 13)
			return;

		if (cur == 13) {
			if (sum == cur)
				t++;
			return;

		} else {
			// 一种牌有4种类型 判断一次持有多少张相同的牌
			for (int i = 0; i < 5; i++) {
				sum += i;
				DFS(cur + 1);
				sum -= i;
			}
		}

	}
	public static void main(String[] args) {
		DFS(0);
		System.out.println(t);
	}
}

感谢这位博主的文章写得非常的好！https://blog.****.net/weiyuefei/article/details/79316653

0-1背包问题(回溯算法)

0-1背包问题

相关推荐