The program question was asked based on this question. Thats all the information was giving for this question.

8. (15 points) Write a C++ program called assignment.cpp that solves the Assignment Problem in Chap 3.4. Your program should read the assignment costs of each person from a user and determine the best assignment. In the program, you can assume that the number of all jobs is less than 15. To get the full credits, your program should display all combinations of assignments. However, the sequence of combinations to be displayed on the screen is not important. This is a sample run Enter number of jobs: 2 Enter assignment costs of 2 persons: Person 1: 2 5 Page 4 of 5 Person 2: 46 Output: Permutation 1: => total cost: 8 Permutation 2: => total cost: 9 Solution: => total cost: 8 This is another sample run Enter number of jobs: 3 Enter assignment costs of 3 persons: Person 1: 2 5 3 Person 2: 4 69 Person 3: 7 2 4 Permutation 1: to tal cost: 12 Permutation 2: => t al cost: 13 Permutation 3: => t cost: 13 Permutation 4: cost: 21 Permutation 5: st: 9 Permutation 6: => st: 16 O O O O DO Solution: => total cost: 9 Assignment Problem In our third example of a problem that can be solved by exhaustive search, there are n people who need to be assigned to execute n jobs, one person per job. (That is, each person is assigned to exactly one job and each job is assigned to exactly one person.) The cost that would accrue if the ith person is assigned to the jth job is a known quantity C[i, j] for each pair i, j = 1, 2, ..., n. The problem is to find an assignment with the minimum total cost. A small instance of this problem follows, with the table entries representing the assignment costs C[i, j]: Job 1 Job 2 Job 3 Job 4 0 Person 1 Person 2 Person 3 Person 4 00+ It is easy to see that an instance of the assignment problem is completely specified by its cost matrix C. In terms of this matrix, the problem is to select one element in each row of the matrix so that all selected elements are in different columns and the total sum of the selected elements is the smallest possible. Note that no obvious strategy for finding a solution works here. For example, we cannot select the smallest element in each row, because the smallest elements may happen to be in the same column. In fact, the smallest element in the entire matrix need not be a component of an optimal solution. Thus, opting for the exhaustive search may appear as an unavoidable evil. We can describe feasible solutions to the assignment problem as n-tuples (1, ..., jn) in which the ith component, i = 1, ..., n, indicates the column of the element selected in the ith row (i.e., the job number assigned to the ith person). For example, for the cost matrix above, (2, 3, 4, 1) indicates the assignment of Person 1 to Job 2, Person 2 to Job 3, Person 3 to Job 4, and Person 4 to Job 1. The requirements of the assignment problem imply that there is a one-to-one correspondence between feasible assignments and permutations of the first n integers. Therefore, the exhaustive-search approach to the assignment problem would require generating all the permutations of integers 1, 2, ..., n, computing the total cost of each assignment by summing up the corresponding elements of the cost matrix, and finally selecting the one with the smallest sum. A few first iterations of applying this algorithm to the instance given above are shown in Figure 3.9; you are asked to complete it in the exercises. [ 9 2 7 8] C6 4 3 7 CE 5 8 1 8 7 6 94 cost = 9+4 + 1 + 4 = 18 cost = 9+4 + 8 + 9 = 30 cost = 9+ 3 + 8 + 4 = 24 cost = 9+ 3 + 8 + 6 = 26 cost = 9 + 7 + 8 + 9 = 33 cost = 9+ 7 + 1 + 6 = 23 etc. FIGURE 3.9 First few iterations of solving a small instance of the assignment problem by exhaustive search. Since the number of permutations to be considered for the general case of the assignment problem is n!, exhaustive search is impractical for all but very small instances of the problem. Fortunately, there is a much more efficient algorithm for this problem called the Hungarian method after the Hungarian mathematicians Knig and Egervry, whose work underlies the method (see, e.g., (Ko195]). This is good news: the fact that a problem domain grows exponentially or faster does not necessarily imply that there can be no efficient algorithm for solving it. In fact, we present several other examples of such problems later in the book. However, such examples are more of an exception to the rule. More often than not, there are no known polynomial-time algorithms for problems whose domain grows exponentially with instance size, provided we want to solve them exactly. And, as we mentioned above, such algorithms quite possibly do not exist