Jeddah Municipality has decided to build a network of national hospitals to treat infectious diseases. A special task force is constituted which is tasked to investigate possible locations for these new hospitals. The task force has done its job and come back with a list of potential sites. Each of these hospitals has an associated cost and will provide coverage to some number of nearby districts within Jeddah. We can represent each potential hospital site as having: a name (string), cost to build the hospital (int) and a set of districts to be covered (Set of
Jeddah Municipality has decided to build a network of national hospitals to treat infectious
diseases. A special task force is constituted which is tasked to investigate possible locations for
these new hospitals. The task force has done its job and come back with a list of potential sites.
Each of these hospitals has an associated cost and will provide coverage to some number of
nearby districts within Jeddah. We can represent each potential hospital site as having: a name
(string), cost to build the hospital (int) and a set of districts to be covered (Set of strings).
Jeddah Municipality is interested in providing health care to all, but they do not have funds to
build an unlimited number of hospitals. The goal is to provide coverage to as many districts as
possible using the available funds. For example, suppose Jeddah Municipality has the following
districts:
Al-Aziziya, Ar-Rihab, Mosharafa, Al-Faysaliya, Bani Malik, An-Naseem, Al-Balad, Al-Salam, AlMakarona, As-Salmiya, Al-Gozain, Al-Hamdaniya
Suppose that these are the possible hospital sites:
Site 1: Covers Al-Aziziya, Ar-Rihab, Mosharafa, Al-Faysaliya. Cost: SARs 20,000,000.
Site 2: Covers Ar-Rihab, Bani Malik, An-Naseem, Al-Balad. Cost: SARs 50,000,000.
Site 3: Covers Al-Balad, Al-Salam, Al-Makarona, As-Salmiya, Al-Gozain. Cost: SARs 40,000,000.
Site 4: Covers As-Salmiya, Al-Gozain, Al-Hamdaniya. Cost: SARs 10,000,000.
Site 5: Covers Mosharafa, Al-Faysaliya, An-Naseem, Al-Balad. Cost: SARs 30,000,000.
Site 6: Covers Al-Balad, Al-Salam, Al-Hamdaniya. Cost: SARs 10,000,000.
Site 7: Covers Al-Balad, Mosharafa, Al-Salam, Al-Makarona, As-Salmiya. Cost: SARs 60,000,000.
Site 8: Covers Ar-Rihab, Bani Malik, Al-Makarona, As-Salmiya, Al-Balad. Cost: SARs 50,000,000.
If you build Site 1 and Site 2, you have provided coverage to Al-Aziziya, Ar-Rihab, Mosharafa, AlFaysaliya, Bani Malik, An-Naseem, and Al-Balad a total of seven districts, at a cost of SARs
70,000,000. (Notice that both Site 1 and Site 2 provide coverage to Ar-Rihab, so even though
Site 1 and Site 2 cover four districts each, only seven total districts end up covered). Adding in
Site 5 would add in a cost of SARs 50,000,000 without actually providing any new coverage,
since all four of the cities it services are already covered.
Your task is to write a recursive function that takes as input a list of possible hospital sites and
an amount of funds available, and then returns a list of hospitals that should be built to provide
coverage to the maximum number of cities.
It is important to note that multiple hospitals could provide coverage to the same district.
However, , when you count up the total number of districts covered, you do not double-count a
district.
sample output : Suppose total available funds (budget) are: SARs 80,000,000. The optimal coverage is [Site 1,
Site 4, Site 5, Site 6] covers 11 districts.
input file :
80000000 8 Site1 Al-Aziziya Ar-Rihab Mosharafa Al-Faysaliya Cost 20000000 Site2 Ar-Rihab Bani Malik An-Naseem Al-Balad Cost 50000000 Site3 Al-Balad Al-Salam Al-Makarona As-Salmiya Al-Gozain Cost 40000000 Site4 As-Salmiya Al-Gozain Al-Hamdaniya Cost 10000000 Site5 Mosharafa Al-Faysaliya An-Naseem Al-Balad Cost 30000000 Site6 Al-Balad Al-Salam Al-Hamdaniya Cost 10000000 Site7 Al-Balad Mosharafa Al-Salam Al-Makarona As-Salmiya Cost 60000000 Site8 Ar-Rihab Bani-Malik Al-Makarona As-Salmiya Al-Balad Cost 50000000
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
