数据结构与算法 / 回溯算法（八皇后、0 - 1 背包）

回溯算法，顾名思义，就是在没有得到最优解的前提下，不断的返回至前面的岔路口位置，重新选择，直至遍历了所有的情况或者得到的预期最优解的情况下再结束。

与贪心算法不同的是，回溯算法理论上是可以得到最优解，而贪心算法则尽可能在快的情况下得到较理想的结果。

一、八皇后

下面的栗子就是八皇后问题，是一个典型的回溯算法应用栗子。其实本质上就是遍历所有的可能性，最后满足条件者打印出来。 

#include unsigned int g_count = 0;bool isOK(unsigned char *p_result, const unsigned char &row, const unsigned char &column);
void PrintResult(unsigned char *p_result);
void Calc8Queens(unsigned char *p_result, const unsigned char &row);int main()
{unsigned char result[8] = {5, 5, 5, 5, 5, 5, 5, 5};Calc8Queens(result, 0);std::cout << "共有 " << g_count << " 个结果" << std::endl;return 0;
}bool isOK(unsigned char *p_result, const unsigned char &row, const unsigned char &column)
{if (p_result == nullptr)return false;unsigned char leftup = column - 1;unsigned char rightup = column + 1;for (int i = row - 1; i >= 0; --i){if (p_result[i] == column)return false;if (leftup >= 0){if (p_result[i] == leftup)return false;}if (rightup < 8){if (p_result[i] == rightup)return false;}leftup--;rightup++;}return true;
}void PrintResult(unsigned char *p_result)
{if (p_result == nullptr)return;for (unsigned char i = 0; i < 8; ++i){for (unsigned char k = 0; k < p_result[i]; ++k)std::cout << "-"<< " ";std::cout << "a"<< " ";for (unsigned char k = p_result[i] + 1; k < 8; ++k)std::cout << "-"<< " ";std::cout << std::endl;}std::cout << std::endl;std::cout << std::endl;return;
}void Calc8Queens(unsigned char *p_result, const unsigned char &row)
{if (p_result == nullptr)return;if (row >= 8){g_count++;PrintResult(p_result);return;}for (int column = 0; column < 8; ++column){if (isOK(p_result, row, column)){p_result[row] = column;Calc8Queens(p_result, row + 1);}}return;
}

结果太多了，就不写出来了，共有 92 个可能性。 

二、0 - 1 背包

#include unsigned int g_max = 0;
void func(const int &index, const int &cw, const int *const pitems, const int &count, const int &maxW);int main()
{int items[10] = {80, 20, 90, 9, 50, 6, 70, 8, 9, 10};func(0, 0, items, 10, 111);std::cout << "所能容纳的最大的物件重量为 " << g_max << std::endl;return 0;
}void func(const int &index, const int &cw, const int *const pitems, const int &count, const int &maxW)
{if (cw == maxW || index >= count){if (cw > g_max)g_max = cw;return;}func(index + 1, cw, pitems, count, maxW);if (cw + pitems[index] <= maxW)func(index + 1, cw + pitems[index], pitems, count, maxW);return;
}

结果为 110 。

（SAW：Game Over！）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！