最小化成本 [英] Minimizing cost
问题描述
有组和P项.每个组为每个项目花费的成本在2D列表中给出.我想通过最小化成本并添加所有项目来解决此问题.
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 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)
推荐答案
该答案用于原始问题
这是解决问题的一种方法:
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
min_cost_
函数获取患者索引和可用的医生,并从该患者索引开始分配一名医生并处理一个或多个患者(patients_to_treat
).此费用是当前医生处理这些患者的费用(doctor_cost
)+ min_cost_(当前医生不可用的下一个患者索引).然后,将所有可用医生以及医生可以治疗的患者人数的成本降到最低.
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.
由于将存在重复的子问题,因此使用缓存(使用lru_cache
装饰器)来避免重新计算这些子问题.
Since there will be repeated sub-problems, a cache (using the lru_cache
decorator) is used to avoid re-computing these sub-problems.
让M
=医生人数,N
=患者人数.
Let M
= number of doctors and N
= number of patients.
所有 doctor_cost
调用中的时间复杂度为O(M * N^2)
,因为这是可以形成的(doctor_index, patient_start, patient_end)
元组的数量,并且函数本身(除递归调用之外)仅持续不断地工作.
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.
时间复杂度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
的时间复杂度时,我们考虑了对 doctor_cost
的所有可能调用.
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
.
因此,总时间复杂度为O(2^M * M * N^2) + O(M * N^2) = O(2^M * M * N^2)
.
Thus, the total time complexity is O(2^M * M * N^2) + O(M * N^2) = O(2^M * M * N^2)
.
考虑到原始问题的限制(<= 20位患者,<<= 10位医生),时间复杂度似乎是合理的.
Given the constraints of the original problem (<= 20 patients, and <= 10 doctors), the time complexity seems reasonable.
- 可以对这段代码进行一些优化,为简单起见,我省略了它们:
- 为了找到医生的最佳患者人数,我尝试了尽可能多的连续患者(即
patients_to_treat
循环).相反,可以通过二进制搜索找到最佳患者数.这样可以将min_cost_
到O(N * 2^M * M * log(N))
的时间复杂度降低. -
doctor_cost
函数可以通过存储costs
矩阵的每一行的前缀和来计算.即代替[2, 3, 1, 2]
行存储[2, 5, 6, 8]
.这样会将doctor_cost
的时间复杂度降低到O(M * N)
. - 可用医生列表(
available_doctors
)可以是一个位字段(并且由于医生数量<= 10,所以16位整数就足够了)
- 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 ofmin_cost_
toO(N * 2^M * M * log(N))
. - The
doctor_cost
function can be calculated by storing the prefix-sum of each row of thecosts
matrix. i.e. instead of the row[2, 3, 1, 2]
store[2, 5, 6, 8]
. This will reduce the time complexity ofdoctor_cost
toO(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)
这篇关于最小化成本的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
- To find the optimal number of patients for a doctor, I try as many consecutive patients as I can (i.e. the
- 为了找到医生的最佳患者人数,我尝试了尽可能多的连续患者(即