Date: Thursday, April 19th, 2012
We highly encourage being environment friendly and trying all problems on your own.
1． Knapsack Problem. There are 5 items that have a value and weight list below, the
knapsack can contain at most 100 Lbs. Solve the problem both as fractional knapsack and 0/1 knapsack.
2． A simple scheduling problem. We are given jobs j1, j2… jn, all with known running times
t1, t2… tn, respectively. We have a single processor. What is the best way to schedule these jobs in order to minimize the average completion time. Assume that it is a nonpreemptive scheduling: once a job is started, it must run to completion. The following is an instance.
a) (j1, j2, j3, j4) : (15，8，3，10)
3． Single-source shortest paths. The following is the adjacency matrix, vertex A is the
source.
A B C D E
A -1 3 B 3 2 2 C D 1 5 E -3
4． All-pairs shortest paths. The adjacency matrix is as same as that of problem 3.(Use
Floyd or Johnson’s algorithm)
因篇幅问题不能全部显示，请点此查看更多更全内容