Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out an assignment which results in the least total cost. Your task is to write a c++ program to implement the branch and bound algorithm to solve this assignment problem.
Your program should read input data from a input file named "infile.txt". The format for the input file is as follows: First line is an integer N representing the number of agents and the number of jobs. In the next N lines, each line j (1 ≤ j ≤ N) consists of N integers representing the cost of assigning agent j to each of the N tasks.
Figure 1 gives you an example of the input format. For example, the cost of assigning agent 1 to task 1, 2, 3 and 4 are 11, 12, 18 and 40 respectively.
11 12 18 40
14 15 13 22
11 17 19 23
17 14 20 28
Total cost: 61 (1,1) (2,3) (3,4) (4,2)
Output, to standard output, will consist of:
Figure 2 gives you an example of the output screen for the input file in Figure 1.