最小化成本

本文介绍了最小化成本的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

有组和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 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)