Help~算法问题：assignment problem

Question

Give a backtracking algorithm to solve the assignment problem defined as follows.
Given n employees to be assigned to n jobs such that the cost of assigning the ith person to the jth job is ci,j,find an assignment that minimizes the total cost.Assume that the cost is nonnegative,that is, c>=0 for 1<=i,j<=n.
请给出程序，满意加10分，
谢谢！
再追加10分

Answer 1

这是典型的二分图最佳匹配问题，该问题可以抽象如下：
有一左分图和右分图均有n个节点的二分完全图，也就是任意左节点与任意右节点之间都有边直接相连的二分图，并且左边的第i个节点与右边的第j个节点的匹配权值为w(i,j)
现要求出该二分图的一个完全匹配，使得这个匹配的权值之和是所有的的完全匹配中最大的

显然你的那个问题与二分图最佳匹配问题可以互相转化，是完全等价的
把n个雇员作为二分图的左边的节点，把n个职位作为右边的节点，第i个雇员与第j个职位匹配的权值为-c(i,j)，然后要求出这个二分图的最佳匹配

鉴于这个问题完全等同于经典的二分图最佳匹配问题，直接给你程序不太合适，以下这个链接是解二分图最佳匹配问题的经典算法KM算法(Kuhn-Munkres Algorithm)的资料，你照着编写程序就行了

http://cms.bit.edu.cn/moodle/mod/resource/view.php?id=3277
虽然里面的代码是pascal的……不过凑合一下吧，而且还有例题