最小化成本

Question

有组和p项。每组为每个项目花费的成本在2D列表中给出。我想通过最小化成本和添加所有项目来解决这个问题

for effort in items:
    minE = min(minE , sum(effort))

row = len(items)
col = len(items[0])

itemsEach = []
for i in range(col):
    minm = items[0][i]
    for j in range(1 , row):
        if items[j][i] < minm:
            minm = items[j][i]
    itemsEach.append(minm)
minE = min(minE , sum(itemsEach))
print(minE)

Answer 1

编辑：此答案适用于original question

这里有一种解决方法：

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

min_cost_函数获取可用的患者索引和医生，并从该患者索引开始分配医生，处理一个或多个患者（patients_to_treat）。其成本是当前医生处理这些患者的成本（doctor_cost）+最小成本（当前医生不可用的下一个患者指数）。然后，在所有可用的医生和医生可以治疗的患者数量上，成本最小化

因为会有重复的子问题，所以使用缓存（使用lru_cache装饰器）来避免重新计算这些子问题

时间复杂性

设M=医生人数N=患者人数

对doctor_cost的所有调用的时间复杂度为O(M * N^2)，因为这是可以形成的(doctor_index, patient_start, patient_end)元组的数量，而函数本身（递归调用除外）只做常量工作

时间复杂度min_cost_为O((N * 2^M) * (M * N)) = O(2^M * M * N^2)N * 2^M是可以形成的(patient_index, available_doctors)对的数量，M * N是函数（递归调用除外）所做的工作doctor_cost在这里可以被认为是O（1），因为在计算doctor_cost的时间压缩性时，我们考虑了所有可能的调用

因此，总时间复杂度为O(2^M * M * N^2) + O(M * N^2) = O(2^M * M * N^2)

考虑到原始问题的限制条件（<；=20名患者和<；=10名医生），时间复杂性似乎是合理的

其他说明：

• 为了简单起见，我省略了对这段代码的一些优化：
  • 为了找到医生的最佳患者数量，我尝试尽可能多的连续患者（即patients_to_treat循环）。相反，可以通过二进制搜索找到最佳患者数量。这将把min_cost_的时间复杂度降低到O(N * 2^M * M * log(N))
  • doctor_cost函数可以通过存储costs矩阵每行的前缀和来计算。i、 e.代替行[2, 3, 1, 2]存储[2, 5, 6, 8]。这将把doctor_cost的时间复杂度降低到O(M * N)
  • 可用医生列表（available_doctors）可以是一个位字段（由于医生数量<；=10，16位整数就足够了）
• 这个问题与{a2}非常相似，因为医生治疗患者的不同费用增加了复杂性
• 运行this repl以可视化算法选择的最佳解决方案