原来的工作分配问题,限时为10秒,所以不剪枝也能AC,本题的工作分配要求还是一样,但限时要求为1秒,所以本题要求用到剪枝函数。
剪枝函数的初步思路,就是在回溯搜索过程中,如果当前成本超过了已经搜索到的分配方案的成本,那么就这个分枝就没有搜索的意义,应该剪去。
稍微深入的想法是,就算当前费用小于已经搜索到的分配方案的费用,难道就一定有搜索的价值吗?也是未必,毕竟当前费用只包含了前面几项工作分配的所需费用,如果加上后面剩余工作的分配费用,那么就很可能超过已经搜索到的分配方案的费用。那么,如何估算剩余工作的分配费用?,每项工作,都可以算出最少费用,每项剩余工作的最少费用之和,是剩余工作的分配费用的下限。当前成本加上每项剩余工作的最少费用之和,应该小于已经搜索到的分配方案的费用。
本题要求按照这种深入的想法,去编写剪枝函数bound,以提高搜索的效率。
第一行有1 个正整数n (1≤n≤20)。接下来的n行,每 行n个数,表示工作费用。
将计算出的最小总费用输出
3 10 2 3 3 3 4 3 4 5
9
回溯法基础练习,第1题可以不剪枝,第2题必须剪枝。,希望都练习一下