Minimizing Cost

There are groups and P items. The cost taken by each group for each item is given in a 2D List. I want to solve this problem by minimizing the cost and by adding all the items. for

Solution 1:

Edit: This answer is for the original question.

Here is one way to solve it:

from functools import lru_cache


def min_cost(costs) -> int:
    num_doctors = len(costs)
    num_patients = len(costs[0])

    @lru_cache(None)
    def doctor_cost(doctor_index, patient_start, patient_end) -> int:
        if patient_start >= patient_end:
            return 0
        return costs[doctor_index][patient_start] + doctor_cost(
            doctor_index, patient_start + 1, patient_end
        )

    @lru_cache(None)
    def min_cost_(patient_index, available_doctors) -> float:
        if all(not available for available in available_doctors) or patient_index == num_patients:
            return float("+inf") if patient_index != num_patients else 0

        cost = float("+inf")
        available_doctors = list(available_doctors)
        for (doctor_index, is_doctor_available) in enumerate(available_doctors):
            if not is_doctor_available:
                continue

            available_doctors[doctor_index] = False
            for patients_to_treat in range(1, num_patients - patient_index + 1):
                cost_for_doctor = doctor_cost(
                    doctor_index, patient_index, patient_index + patients_to_treat
                )
                cost = min(
                    cost,
                    cost_for_doctor
                    + min_cost_(
                        patient_index + patients_to_treat, tuple(available_doctors)
                    ),
                )
            available_doctors[doctor_index] = True

        return cost

    return int(min_cost_(0, tuple(True for _ in range(num_doctors))))


assert min_cost([[2, 2, 2, 2], [3, 1, 2, 3]]) == 8

The min_cost_ function takes a patient index and doctors that are available and assigns a doctor starting at that patient index and handling one or more patients (patients_to_treat). The cost of this is the cost of the current doctor handling these patients (doctor_cost) + min_cost_(the next patient index with the current doctor being unavailable). The cost is then minimized over all available doctors and over the number of patients a doctor can treat.

Since there will be repeated sub-problems, a cache (using the lru_cache decorator) is used to avoid re-computing these sub-problems.

Time complexity

Let M = number of doctors and N = number of patients.

The time complexity across all calls to doctor_cost is O(M * N^2) since that is the number of (doctor_index, patient_start, patient_end) tuples that can be formed, and the function itself (apart from recursive calls) only does constant work.

The time complexity min_cost_ is O((N * 2^M) * (M * N)) = O(2^M * M * N^2). N * 2^M is the number of (patient_index, available_doctors) pairs that can be formed, and M * N is the work that the function (apart from recursive calls) does. doctor_cost can be considered O(1) here since in the calcuation of time compelxity of doctor_cost we considered all possible calls to doctor_cost.

Thus, the total time complexity is O(2^M * M * N^2) + O(M * N^2) = O(2^M * M * N^2).

Given the constraints of the original problem (<= 20 patients, and <= 10 doctors), the time complexity seems reasonable.

Other notes:

• There are some optimizations to this code that can be made that I've omitted for simplicity:
  • To find the optimal number of patients for a doctor, I try as many consecutive patients as I can (i.e. the patients_to_treat loop). Instead, the optimal number of patients could be found by binary search. This will reduce the time complexity of min_cost_ to O(N * 2^M * M * log(N)).
  • The doctor_cost function can be calculated by storing the prefix-sum of each row of the costs matrix. i.e. instead of the row [2, 3, 1, 2] store [2, 5, 6, 8]. This will reduce the time complexity of doctor_cost to O(M * N).
  • The list of available doctors (available_doctors) could be a bit field (and since number of doctors <= 10, a 16 bit integer would suffice)
• This question is quite similar to the painter's partition problem with the added complexity of different costs for a doctor to treat a patient.
• Run this repl for a visualization of what the algorithm picks as an optimal solution.