find_addends
find_addends_backpack01float
find_addends_backpack01float
- dramkit.find_addends.find_addends_backpack01float.find_addends_backpack01float(tgt_sum, alts)
- 从给定的列表alts（正数）中选取若干个数，其和小于等于tgt_sum并且最接近sum_tgt思路：求和问题转化为物品价值和重量相等的01（正）浮点数背包问题
- Parameters:
tgt_sum (float) – 目标和
alts (list) – 备选加数列表
- Returns:
max_v (float) – 最近接tgt_sum的最大和
addends (list) – 和为max_v的备选数列表
trace (list) – 与addends对应的备选加数索引
values (list) – 备选数之和跳跃点记录
References
find_addends_backpack01int
find_addends_backpack01int
- dramkit.find_addends.find_addends_backpack01int.find_addends_backpack01int(tgt_sum, alts)
- 从给定的列表alts（正数）中选取若干个数，其和小于等于tgt_sum并且最接近sum_tgt思路: 求和问题转化为物品价值和重量相等的01（正）整数背包问题缺点: 浪费空间
- Parameters:
tgt_sum (float) – 目标和
alts (list) – 备选加数列表
- Returns:
max_v (float) – 最近接tgt_sum的最大和
trace (list) – 和为max_v的备选数列表
References
find_addends_bigfirst
find_addends_bigfirst
- dramkit.find_addends.find_addends_bigfirst.find_addends_bigfirst(tgt_sum, alts, n_adds=None, check_alts=False, add_num=None, tol_below=0.0, tol_above=0.0, max_loop=1000000, global_loop=False, log_info=False, save_process=False, logger=None)
- 从给定的列表alts（可以有负数）中选取若干个加数之和最接近tgt_sum，大的备选数优先思路: 从大到小依次加入备选数若加入新值之后找不到理想解，则删除最后加入的值，继续添加下一个更小的备选数下一个备选数确定方式：当alts中只有正数时，剩下的数中与剩余和（目标和减去当前和）最接近的数当alts中有负数时，直接取比最后加进去的数更小的数（搜索速度会变慢很多）
- Parameters:
tgt_sum (float, int) – 目标和
alts (list) – 备选数列表
n_adds (int) – 限制备选加数个数为n_adds，默认无限制
check_alts (bool) –
是否检查alts（提前删除大于目标和的备选数），默认否注：该参数只有当alts没有负数时才起作用add_num (int) – 在加起来和大于等于tgt_sum的基础上增加的备选数个数，意义同
dramkit.find_addends.find_addends_utils.get_alts_sml()函数中的add_num参数，在check_alts起作用时才起作用tol_below (float) – 下界误差，若目标和减去当前和小于等于tol_below，则结束搜索，默认为0.0
tol_above (float) – 上界误差，若当前和减去目标和小于等于bol_above，则结束搜索，默认为0.0
max_loop (int) – 最大搜索次数限制，默认一百万
global_loop (bool) – 是否将寻找下一个最优备选数时的循环次数计入总搜索次数
log_info (bool) – 是否打印搜索次数和时间等信息
save_process (bool) – 是否保存搜索过程
logger (Logger) – logging日志记录器
- Returns:
choseds_best (list) – 最优备选数列表
choseds_addends (list) – 最终备选数列表
adds_process (list) – 搜索中间过程
find_addends_recu
find_addends_recu
- dramkit.find_addends.find_addends_recu.find_addends_recu(tgt_sum, alts, max_idx, choseds=[], results=[], tol_below=0.0, tol_above=0.0, n_result=None, keep_order=True)
- 递归方法，从给定的列表alts中选取若干个数之和最接近tgt_sum优点: 可在实数范围内求解，没有正负或整数限制；能够返回所有可行解（理论上）缺点: 受递归深度限制，alts太长就无法求解；没有可行解的情况下不能返回相对最优解？
- Parameters:
tgt_sum (float, int) – 目标和
alts (list) – 备选数列表
max_idx (int) – 从索引max_idx处开始从后往前搜索，初始值一般设为alts的最大索引
choseds (list) – 预选中的备选数，初始值默认为空
results (list) – 已存在的所有结果，初始值默认为空
tol_below (float) – 下界误差，若目标和减去当前和小于等于tol_below，则为可行解，默认为0.0
tol_above (tol) – 上界误差，若当前和减去目标和小于等于bol_above，则为可行解，默认为0.0
n_result (int, None) – 返回的可行解个数限制，当results的长度大于n_result时返回results
keep_order (bool) – 是否保结果中备选数的进入顺序与alts中的顺序一致，默认是
- Returns:
results – 所有可能的解列表
- Return type:
list
References
find_addends_smlfirst
find_addends_smlfirst
- dramkit.find_addends.find_addends_smlfirst.find_addends_smlfirst(tgt_sum, alts, n_adds=None, tol_below=0.0, tol_above=0.0, max_loop=1000000, global_loop=False, log_info=False, save_process=False, logger=None)
- 从给定的列表alts（可以是负数）中选取若干个加数之和最接近tgt_sum，小的备选数优先只不过小的数优先，从而避免了有负数时找不到最优解的情况
- Parameters:
tgt_sum (float, int) – 目标和
alts (list) – 备选数列表
n_adds (int) – 限制备选加数个数为n_adds，默认无限制
tol_below (float) – 下界误差，若目标和减去当前和小于等于tol_below，则结束搜索，默认为0.0
tol_above (float) – 上界误差，若当前和减去目标和小于等于bol_above，则结束搜索，默认为0.0
max_loop (int) – 最大搜索次数限制，默认一百万
global_loop (bool) – 是否将寻找下一个最优备选数时的循环次数计入总搜索次数
log_info (bool) – 是否打印搜索次数和时间等信息
save_process (bool) – 是否保存搜索过程
logger (Logger) – logging日志记录器
- Returns:
choseds_best (list) – 最优备选数列表
choseds_addends (list) – 最终备选数列表
adds_process (list) – 搜索中间过程
find_addends_utils
tol2side_x_eq_y
- dramkit.find_addends.find_addends_utils.tol2side_x_eq_y(x, y, tol_below=0.0, tol_above=0.0)
在上界误差tol_above和下界误差tol_below范围内判断x是否等于y
tol_eq
- dramkit.find_addends.find_addends_utils.tol_eq(x, y, tol=0.0)
在绝对误差tol范围内判断x和y相等
tol_x_big_y
- dramkit.find_addends.find_addends_utils.tol_x_big_y(x, y, tol=0.0)
在绝对误差tol范围外判断x大于y
tol_x_big_eq_y
- dramkit.find_addends.find_addends_utils.tol_x_big_eq_y(x, y, tol=0.0)
在绝对误差tol范围内判断x大于等于y
tol_x_sml_y
- dramkit.find_addends.find_addends_utils.tol_x_sml_y(x, y, tol=0.0)
在绝对误差tol范围外判断x小于y
tol_x_sml_eq_y
- dramkit.find_addends.find_addends_utils.tol_x_sml_eq_y(x, y, tol=0.0)
在绝对误差tol范围内判断x小于等于y
get_alts_sml
- dramkit.find_addends.find_addends_utils.get_alts_sml(tgt_sum, alts, sort_type='descend', tol=0.0, add_num=None)
从给定备选列表alts中挑选出和小于等于tgt_sum的可行备选数
- Parameters:
tgt_sum (float, int) – 目标和
alts (list) – 备选数列表
sort_type (str) – 对alts进行排序的方式，默认’descend’降序，可选’ascend’升序、None不排
tol (float) – 两个数进行比较时的绝对误差控制范围
add_num (int, None) – 限制在加起来和大于等于tgt_sum的基础上增加的备选数个数，默认无限制
- Returns:
alts – 可行备选数列表
- Return type:
list
backfind_sml1st_index
- dramkit.find_addends.find_addends_utils.backfind_sml1st_index(tgt_sum, alts, tol=0.0, loop_count=None)
alts从后往前搜索，返回第一个小于等于tgt_sum的数的索引
- Parameters:
tgt_sum (int, float) – 目标值
alts (list) – 待比较数列表
tol (float) – 两个数进行比较时的绝对误差控制范围
loop_count (int) – 初始迭代次数值，默认为None；若loop_count为None，则不记录迭代次数， 否则在loop_count基础上继续记录迭代次数
- Returns:
idx (int) – 从后往前搜索，alts中小于等于tgt_sum的第一个数的索引
loop_count (int) – 搜索结束时的迭代次数