Algorithms留学生讲解、辅导PYTHON/JAVA编程、讲解Java/c++

Introduction to Algorithms Assignment3

Due Date: 2019/01/04 12:00:59

Resource Allocation Problem

Given m resources and n projects, a profit( i, j) will be obtained if j, resources are allocated to project i.

Find an allocation of resources to maximize the total profit.

Please use dynamic programming approach to design an algorithm and

implement the program to solve the resource allocation problem.

e.g. You have 7 days to study four courses. Each course should study at least 1

day. How to plan your schedule to get the highest score?

Days to study course

1 2 3 4

1 3 4 3 6

2 6 6 4 7

3 7 9 8 9

4 8 11 9 10

Answer: max score is 24.

P.S. If you study course 1 two days, you will get 6 points.

Input:

3 4 3 6

6 6 4 7

7 9 8 9

8 11 9 10(profit table)

7(resource)

3 4 3

6 6 4

7 9 8

8 11 9

6

Output:

24(6+9+3+6)

18(6+9+3)

Rule of programing and the dataset:

(1) Resources is larger than number of plans (Because one plan need to choose

once)

(2) One profit table may contain more than one allocation problem

(3) All element type is positive Integer.

(4) Cannot use not standard header file(e.g <bits/stdc++>) or you should attach

on your zip

(5) Input and output txt file automatically and the relative path is beside the

main program