再次提问：一个算法问题向大家请教，500分＋1顿饭。

Question

问题简述：现有一个m行n列的平面网格，{a(i,j)}代表各个位置的权重。现有k种不同面值的硬币，面值分别是 b(1),b(2),...,b(k)（各不相同），硬币的个数分别是
d(1),d(2),...,d(k),d(1)+d(2)+...+d(k)（记做d）不超过m*n。问：在保证相同面值的硬币位置相邻（某一位置至多4个相邻位置，对角线不算相邻）的条件下，如何安排这d个硬币的位置，使得
    所有位置的指标（a(i,j)*[a(i,j)位置处放置的硬币的面值]）之和（记做S）
                   
最小？
补：（1）如果某一位置没有硬币，则 该位置处硬币的面值=0；
（2）如果没有办法找到最优解，使S尽可能地小也可以，但必须保证相同面值的硬币位置相邻。

Answer 1

提供一个思路，可能是最小的解。为叙述方便暂时称为最小。
假设放入d(1),d(2),...,d(k)已经是最小了。那么从d(1),d(2),...,d(k)中取出一个d(i)，同时所有d(i)的权值和为最大。那么剩下的k-1种硬币在网格中的放置也是最小的。依次类推，我们可以知道最后剩下的d(j)在网格中的放置
也是最小的。由此，可以得出思路，从k个d(1),d(2),...,d(k)中选取一个d(i)放入让他最小，然后依次放入其他的并让他在剩余的网格中最小，就可以
得到整体的最小放置办法。
这样问题化解为放入k个面值相同的硬币k<m*n并相邻，如何使其权值最小。
先让按大小排序，然后给出a(i,j）相邻矩阵，然后么，最笨的办法就是穷举
了。

Answer 2

我对相邻的理解是这样的。
如果第一个放在（k,j),那么第二个只能在(k-1,j),(k,j-1),(k+1,j),(k,j+1)中选了，其余类推

Answer 3

（1）偶错了：其实上面的第二步是可以终止的， sun_is_shining(流云)的本意应该是当找不到满足条件的交换时即终止。问题在于如何找出（所有的）满足条件的（两个格子的）交换。
（2）最大的问题在于：有可能A和B的交换，不满足条件，B和C的交换，也不满足条件；但是，你把两次交换同时进行，就满足条件了！所以上面sun_is_shining(流云)提供的思路应该是不行的。

Answer 4

（1）偶错了：其实上面的第二步是可以终止的， sun_is_shining(流云)的本意应该是当找不到满足条件的交换时即终止。问题在于如何找出（所有的）满足条件的（两个格子的）交换。
（2）最大的问题在于：有可能A和B的交换，不满足条件，B和C的交换，也不满足条件；但是，你把两次交换同时进行，就满足条件了！所以上面sun_is_shining(流云)提供的思路应该是不行的。