有组和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)
编辑:此答案适用于original question
这里有一种解决方法:
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位整数就足够了)相关问题 更多 >
编程相关推荐