1348 问题 B: 工作分配问题之剪枝函数

时间限制: 1s 内存限制: 128MB 提交: 9 解决: 8
题目描述

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

输入

 第一行有1 个正整数n (1≤n≤20)。接下来的n行,每 行n个数,表示工作费用。

输出

将计算出的最小总费用输出

样例输入
3
10 2 3
3 3 4
3 4 5
样例输出
9
提示

比赛公告

回溯法基础练习,第1题可以不剪枝,第2题必须剪枝。,希望都练习一下