Problem
A team of N doctors are working in a hospital emergency room after an earthquake. The doctors are all on the same shift, which is SHIFT hours long. There are a number of wounded patients. Each patient has a probability (as a percentage) of survival if not treated, a time (in hours) required to treat them, and a probability (as a percentage) of survival if treated. This data is encoded in an array strings PATIENTS, each element describing one patient in the form:
“<TREATED> <UNTREATED> <TREATMENT_TIME>”
e.g “56 78 5″ means the patient has a 56% change of survival if untreated, or a 78% chance of survival after treatment, which takes 5 hours
You should return the maximum expected number of surviving patients.
double expectedSurvivors(int n,int shift,string []patients)
Notes:
- each patient can only be treated by one doctor
Constraints:
- n is between 1 and 10 inclusive
- shift is between 1 and 100 inclusive
- patients has between 1 and 50 elements inclusive
- each element of patients has only whitespace and numerical digits
- for each element of patients, TREATED and UNTREATED are between 0 and 100, inclusive
- for each element of patients, TREATMENT_TIME is between 1 and shift, inclusive
You can post code… but I can’t actually test it.
April 1, 2008 at 3:17 pm |
Since treating a patient adds p_treated – p_untreated to the overal number of expected survivals, this problem collapses exactly to the multiple knapsack problem, see http://en.wikipedia.org/wiki/List_of_knapsack_problems
I think there is unlikely to be any feasible exact solution within the constraints you give, but given how similar it is to the bin-packing problem, there might be some good heuristics, maybe even some with tight bounds.