今天来介绍一下一个比较简单的数据结构——并查集。

勤奋的又更新博客了，这次是破坏正方形问题。

题目

经过了一系列蛋疼的气人的事件之后，终于可以稳定地继续日更博客了。

又是一题IDA*的题目，这题目很像埃及分数。

你没看错又是关于IDA*的题目，那是因为我正在刷刘老师的例题和习题。。。

这次的IDA*也是非常具有标志性的题，确实以后碰到这种状态空间搜索IDA*是一个非常不错的选择。

题目

传送门：https://vjudge.net/problem/UVA-12325

这次介绍一个稍微看起来没有特别多技术含量的题目，叫做宝箱。

这个场景是这样子滴，首先，我们有一个背包，放在我们面前有无限多的两种宝藏，第一种体积为s1价值为v1,第二种体积为s2价值为v2,我们必须想出一种拿宝物的策略使得在我们有限背包内装的宝藏价值最大。

我们分析下这个问题，如果一种宝藏的体积非常大，我们枚举的个数就会非常少，情况就会变少，所以我们这么暴力求解就可以提高效率。

那么，如果两者的以及都非常小呢，那我们通过思考，可以得出这么一个规律，当两者的体积都很小时，我们分别对s1×v2与s2×v1进行计算，假设我们算出了s1×v2>s2×v1,那么我们可以得到说价值为v1的宝物的个数绝对不会超过（s2-1），为什么呢？因为一旦价值为v1的宝物我们拿了s2个，那我们完全可以把s2个价值v1的宝物兑换成总价值更高的s1个价值为v2的宝物。所以通过以上论证我们就可以得出暴力枚举的上限。

迭代加深搜索 + 启发式搜索（A*） = IDA*

这次所介绍的算法用到了前一篇文章（埃及分数）中介绍过的迭代加深搜索，不熟悉迭代加深搜索的同学建议先看我前一篇文章，介绍IDA*之前，让我们先普及一下A*算法，我后续也会写关于A*算法的题目。

问题引入

今天的主题是迭代加深搜索，著名的埃及分数问题（古埃及的智慧。。哈哈)。

高产的我又来了，今天讲的是一个老盆友——BFS。

好不容易建完了博客，当然要发一篇助助兴了，今天就是我拖了两天的倒水问题，对于这道题我也是给上了隐式图的标签，因为这个BFS藏得还是有点深的。