Each programming division is limited in how effectively it can utilize any new resources. For example, one particular division will be able to use 0, 3, 5, or 6 new programmers effectively. (The personnel organization within that division prevents it from being able to use 1, 2, 4, 7 or more new programmers.) This gives 4 options for allocating new programmers to that division. There are only 3 different options for allocation of additional money to that division. Therefore, there are 12 possible allocation scenarios in this example. For each scenario, the company has estimated the incremental lines of code that would be produced by that division.
You must write a program that recommends a precise allocation of resources among the divisions. For each division, your program must determine how many new programmers and how much money should be allocated. Allocation of new programmers and money must be made to maximize the total productivity increase--the sum of incremental lines of code over all divisions. The total number of programmers allocated cannot exceed the total number of programmers that the company is willing to hire. The total amount of money cannot exceed the total amount budgeted for the entire company. In the case where there are multiple optimal solutions, your program may recommend any one of them.
- number of programming divisions (0 < d <= 20 except when d is the end-of-file sentinel)
- total number of new programmers
- total amount of money budgeted for new computing resources
Following those 3 lines are input records for each programming division. The first record is for division #1, the second for division #2, etc. Each division record is organized as follows:
It is possible to allocate 0 new programmers to any division and $0 for new hardware and software--resulting in no increase in productivity for that division. This "null" allocation will be explicitly shown.
- number of new programmer options (0 <= n <= 10)
- x1 x2...xn
- list of new programmer options (numbers are separated by blanks)
- number of new budget options (0 < k < 10)
- b1 b2...bk
- cost of each new budget option (separated by blanks)
- n x k table of integers
- the (i, j) table entry is the incremental lines of code produced for allocation of xi new programmers and bj additional budget
Each allocation problem begins on a new line. The end of input is signified by an allocation "problem" with 0 divisions. No input lines follow that line.
Output for each division comes next. The first line identifies the division by number. The remaining 3 lines indicate the division's budget, the number of new programmers for the division, and the expected incremental lines of code to be produced. One blank line appears between output for successive divisions. Two blank lines appear between output for successive problems. The exact formatting of the output is not critical, but all output must be easy to read and well-identified.
A sample input file which contains one complete allocation problem is shown below. In this problem, there are 3 programming divisions. The company is willing to hire up to 10 new programmers and spend up to $90,000 on new computing resources. For division #1, the expenditure of $50,000 on new computing resources and allocation of 6 new programmers would result in the production of 40,000 incremental lines of code.
3 10 90000 4 0 2 5 6 4 0 20000 50000 70000 0 10000 20000 50000 60000 20000 10000 40000 20000 10000 30000 40000 30000 10000 40000 30000 5 0 1 3 4 8 3 0 40000 80000 0 50000 30000 50000 40000 60000 20000 30000 50000 80000 90000 50000 30000 40000 70000 3 0 4 6 5 0 50000 30000 40000 50000 0 30000 50000 60000 30000 10000 20000 30000 40000 50000 20000 30000 40000 50000 60000 0
Optimal resource allocation problem #1 Total budget: $80000 Total new programmers: 6 Total productivity increase: 210000 Division #1 resource allocation: Budget: $0 Programmers: 2 Incremental lines of code: 60000 Division #2 resource allocation: Budget: $40000 Programmers: 4 Incremental lines of code: 90000 Division #3 resource allocation: Budget: $40000 Programmers: 0 Incremental lines of code: 60000