python - 查找具有给定数字和列表的边界
问题描述
我遇到了这个问题。给定一个百分比 = [0.1,0.1,0.8] 和数字 = 9 的列表,找到与百分比列表相乘的所有可能列表(每个元素的边界为 0.25 到 10,增量 = 0.25),将这些数字相加并四舍五入1 位小数必须等于 number = 9。我使用蛮力算法在 itertools 产品的帮助下解决了这个问题。但是这种蛮力方法很慢。我正在尝试为我的'for循环'找到一个边界(范围内的上下边界(下边界,上边界,25)。你们能建议我找到它的方法吗?
import itertools
ranges = []
n = int(input()) #number of element in percentage list
percent = []
for i in range(n):
percent.append(float(input())) #input the percentage list
total = float(input()) #the number mentioned above
for i in range(n):
ranges.append(range(25,1025,25)) #find boundary for this line
for xs in itertools.product(*ranges):
avg = 0
for i in range(n):
avg += xs[i]*percent[i]
if avg < (total*100+5) and avg >= (total*100-5):
for each in xs:
print(each/100, end = ' ')
print()
解决方案
用简洁的话来解释算法对我来说有点困难 TT
因此,以下代码注释中说明了充分的解释。
基本思想是这是以递归方式完成的(DFS,深度优先搜索)。该功能应该类似于recursion(percent_list, result_list, target)
.
- 一开始应该是
recursion([0.1, 0.1, 0.8], [], 9)
- 如果我们尝试将第一个值设为 3.25,那么我们将目标值更新为 9 - 3.25*0.1 = 8.675。所以我们接下来打电话
recursion([0.1, 0.8], [3.25], 8.675)
; - 然后,我们尝试将第二个值设为 4.00,然后将目标值更新为 8.675 - 4.0*0.1 = 8.275。所以打电话
recursion([0.8], [3.25, 4.0], 8.275)
; - 最后,我们尝试第三个值,只有 9.75,10 是有效的,因为相加的值分别是 8.525 和 8.725,并且可以四舍五入到 9。所以我们将结果附加到结果列表中
[3.25, 4.0, 9.75]
。[3.25, 4.0, 10.0]
- 之后,我们尝试将第二个值设为 0.25, ..., 3.75, 4.25, 4.5, ..., 10。
- 尝试将第一个值设为 0.25, ..., 3.0, 3.5, 3.75, ..., 10。
为了避免过多的递归调用,我们需要计算每次可以附加到结果的有效值,以削减不可能的分支。
实际的函数签名在某种程度上有所不同,以实现向上取整。
import numpy as np
def recursion(percent_list, value_list, previous_results, target, tolerate_lower, tolerate_upper, result_list):
# change , 0.25 ~ 10 , change, , change, 0.5 = 9.5-9 , 0.4999 < 9-8.5, your answer
# init: [0.1,0.1,0.8] [] 9
# if reach the target within tolerate
if len(percent_list) == 0:
# print(previous_results)
result_dict.append(previous_results)
return
# otherwise, cut impossible branches, check minimum and maximum value acceptable for current percent_list
percent_sum = percent_list.sum() # sum up current percent list, **O(n)**, should be optimized by pre-generating a sum list
value_min = value_list[0] # minimum value from data list (this problem 0.25)
value_max = value_list[-1] # maximum value from data list (this problem 10.0)
search_min = (target - tolerate_lower - (percent_sum - percent_list[0]) * value_max) / percent_list[0] # minimum value acceptable as result
search_max = (target + tolerate_upper - (percent_sum - percent_list[0]) * value_min) / percent_list[0] # maximum value acceptable as result
idx_min = np.searchsorted(value_list, search_min, "left") # index of minimum value (for data list)
idx_max = np.searchsorted(value_list, search_max, "right") # index of maximum value (for data list)
# recursion step
for i in range(idx_min, idx_max):
# update result list
current_results = previous_results + [value_list[i]]
# remove the current state for variables `percent_list`, and update `target` for next step
recursion(percent_list[1:], value_list, current_results, target - percent_list[0] * value_list[i], tolerate_lower, tolerate_upper, result_list)
为了解决当前的这个问题,
result = []
recursion(np.array([0.1, 0.1, 0.8]), np.arange(0.25, 10.25, 0.25), [], 9, 0.5, 0.49999, result)
总共有 4806 个可能的结果。验证结果总计约 9 个(但无法验证结果就足够了),
for l in result:
if not (8.5 <= (np.array([0.1, 0.1, 0.8]) * np.array(l)).sum() < 9.5):
print("Wrong code!")
我认为最复杂的情况仍然是 O( m ^ n * n ),如果m指的是数据列表长度 (0.25, 0.5, ..., 10),而n指的是百分比列表长度 (0.1, 0.1, 0.8) . 应该进一步优化到 O( m ^ n * log( m )),避免每次递归求和百分比列表;而对于 O( m ^ n ),如果我们能充分利用数据列表的等差数列的性质。
推荐阅读
- python - 实现 cdc 但在 Python Pandas 中出现值错误
- prometheus - PromQL - 计算指标具有相同值的次数
- java - 无法使用 AdminClient deleteTopic 删除 Kafka 主题
- css - 将 Bootstrap 选择器字段的标题对齐到右侧
- python - 使用 PyArg_ParseTuple 时第一个参数错误
- java - 为什么在创建单例时构造函数是默认的?
- git - 如何使用 git bash 在 git 中暂存单行?
- java - 如何使用流比较列表的元素?
- mysql - 插入到 SIMILAR 键更新时从不同表中选择
- angular - 使用@ngrx/data,得到“没有实体类型 [x] 的实体定义”