From Problem of the Week Department of Physics at Harvard University
Another Question is selected from a anynomous blog, it is somehow similar with those problem could be solved using PERT(Program Evaluation and Review Technique), but the difference is that this problem acquires multiply programs, therefore the whole question is more difficult. It is rather harder to come out with a feasible algorithm.
The problem states:
There are n projects in total, and every project has multiply steps to finish. Every step is marked and there will be k people to work on those projects.
The rules are following: every person can finish one step at a time, and every step is specified to one person. The project should be completed within strict order. Therefore step 2 can not be completed until step 1 is completed. If a person finishes his work, he can immediately be assigned to another work.
The problem ask you to find a optimized solution.
Input:
2 3 (indicates there are 2 projects and 3 people)
3 1 2 2 3 3 5(project 1 is composed by 3 steps, the first step consumes 2 hour and must be completed by person 1, the second step consumes 3 hours and must be completed by person 2, the third step consumes 5 hours and must be completed by person 3)
2 2 3 3 2(project 2 is composed by 2 steps, the first step consumes 3 hours and must be completed by person 2, the second step consumes 2 hours and must be completed by person 3)
Output:
11(the minimum hour required to finish all 2 projects)
没有评论:
发表评论