fork download
copy 
  1. from itertools import combinations
  2. import time
  3. import threading
  4. from collections import defaultdict
  5. import math
  6. from multiprocessing import Pool
  7.  
  8. # 配置参数（优化阈值）
  9. TARGET = 255966  # 目标值
  10. BASE_VALUES = [36.5, 41.5, 59, 68.5, 74, 91.5]  # 基础系数列表
  11. FLUCTUATION = 1.0  # 系数波动范围
  12. MAX_SOLUTIONS = 3  # 每个组合的最大解数量
  13. SOLVER_TIMEOUT = 180  # 求解超时时间(秒)
  14. THREE_VAR_THRESHOLD = 259000  # 使用三个变量的阈值
  15. PRODUCT_RANGE_THRESHOLD = 129000  # 乘积范围限制阈值
  16. HIGH_TARGET_THRESHOLD = 259000  # 更高目标值阈值
  17. SHOW_PROGRESS = True  # 是否显示进度
  18. MAX_SOLUTIONS_PER_COMB = 100  # 每个组合的最大解数量，用于提前终止
  19. USE_MULTIPROCESSING = True  # 是否使用多进程加速
  20.  
  21. def is_valid_product(p):
  22.     """确保单个乘积不超过129000"""
  23.     return p <= 129000  # 严格限制所有乘积不超过129000
  24.  
  25. def find_single_variable_solutions(values):
  26.     """查找单个数的解（a*x = TARGET）"""
  27.     solutions = []
  28.     for a in values:
  29.         quotient = TARGET / a
  30.         if quotient != int(quotient):
  31.             continue
  32.         x = int(quotient)
  33.         if 1 <= x <= 10000 and is_valid_product(a * x):
  34.             solutions.append((a, x))
  35.             if len(solutions) >= MAX_SOLUTIONS:
  36.                 break
  37.     return solutions
  38.  
  39. def find_two_variable_solutions(values):
  40.     """优化的双变量求解算法，确保每个乘积不超过129000"""
  41.     solutions = defaultdict(list)
  42.     for i, a in enumerate(values):
  43.         for b in values[i:]:
  44.             seen_xy = set()
  45.             # 调整x的最大值，确保a*x不超过129000
  46.             max_x = min(math.floor((TARGET - b) / a), math.floor(129000 / a))
  47.             min_x = max(1, math.ceil((TARGET - b * 10000) / a))
  48.  
  49.             if max_x < min_x:
  50.                 continue
  51.  
  52.             x_count = max_x - min_x + 1
  53.             x_step = max(1, x_count // 1000)
  54.  
  55.             for x in range(min_x, max_x + 1, x_step):
  56.                 ax = a * x
  57.                 if ax > 129000:  # 额外检查确保不超过129000
  58.                     continue
  59.  
  60.                 remainder = TARGET - ax
  61.  
  62.                 if remainder < b:
  63.                     break
  64.  
  65.                 if remainder > b * 10000:
  66.                     continue
  67.  
  68.                 if remainder % b == 0:
  69.                     y = remainder // b
  70.                     by = b * y
  71.                     if 1 <= y <= 10000 and by <= 129000:  # 确保b*y也不超过129000
  72.                         xy_pair = (x, y) if a <= b else (y, x)
  73.                         if xy_pair not in seen_xy:
  74.                             seen_xy.add(xy_pair)
  75.                             solutions[(a, b)].append((a, x, b, y))
  76.                             if len(solutions[(a, b)]) >= MAX_SOLUTIONS_PER_COMB:
  77.                                 break
  78.     return solutions
  79.  
  80. def process_three_var_combination(args):
  81.     """处理三变量组合的辅助函数，用于并行计算"""
  82.     a, b, c, value_ranges, target = args
  83.     solutions = []
  84.     seen_xyz = set()
  85.  
  86.     min_x, max_x = value_ranges[a]
  87.     x_count = max_x - min_x + 1
  88.     x_step = max(1, x_count // 1000)
  89.  
  90.     for x in range(min_x, max_x + 1, x_step):
  91.         ax = a * x
  92.         if not is_valid_product(ax):
  93.             continue
  94.  
  95.         remainder1 = target - ax
  96.         if remainder1 < 0:
  97.             break
  98.  
  99.         max_y = math.floor((remainder1 - c) / b)
  100.         min_y = max(1, math.ceil((remainder1 - c * 10000) / b))
  101.  
  102.         if max_y < min_y:
  103.             continue
  104.  
  105.         y_count = max_y - min_y + 1
  106.         y_step = max(1, y_count // 100)
  107.  
  108.         for y in range(min_y, max_y + 1, y_step):
  109.             by = b * y
  110.             if not is_valid_product(by):
  111.                 continue
  112.  
  113.             remainder2 = remainder1 - by
  114.             if remainder2 < 0:
  115.                 break
  116.  
  117.             if remainder2 > c * 10000:
  118.                 continue
  119.  
  120.             if remainder2 % c == 0:
  121.                 z = remainder2 // c
  122.                 if 1 <= z <= 10000 and is_valid_product(c * z):
  123.                     xyz_tuple = tuple(sorted([x, y, z]))
  124.                     if xyz_tuple not in seen_xyz:
  125.                         seen_xyz.add(xyz_tuple)
  126.                         solutions.append((a, x, b, y, c, z))
  127.                         if len(solutions) >= MAX_SOLUTIONS_PER_COMB:
  128.                             return solutions
  129.  
  130.     return solutions
  131.  
  132. def find_three_variable_solutions(values):
  133.     """优化的三变量求解算法，确保每个乘积不超过129000"""
  134.     solutions = defaultdict(list)
  135.     sorted_values = sorted(values)
  136.  
  137.     # 预计算每个系数的有效范围，确保每个乘积不超过129000
  138.     value_ranges = {}
  139.     for a in sorted_values:
  140.         min_x = max(1, math.ceil(1 / a))  # 最小为1
  141.         max_x = min(10000, math.floor(129000 / a))  # 确保a*x <= 129000
  142.         value_ranges[a] = (min_x, max_x)
  143.  
  144.     combinations_list = []
  145.     for i, a in enumerate(sorted_values):
  146.         for j in range(i + 1, len(sorted_values)):
  147.             b = sorted_values[j]
  148.             for k in range(j + 1, len(sorted_values)):
  149.                 c = sorted_values[k]
  150.                 combinations_list.append((a, b, c, value_ranges, TARGET))
  151.  
  152.     if USE_MULTIPROCESSING:
  153.         with Pool() as pool:
  154.             results = pool.map(process_three_var_combination, combinations_list)
  155.  
  156.         for i, (a, b, c, _, _) in enumerate(combinations_list):
  157.             if results[i]:
  158.                 solutions[(a, b, c)] = results[i]
  159.     else:
  160.         total_combinations = len(combinations_list)
  161.         for i, (a, b, c, _, _) in enumerate(combinations_list):
  162.             res = process_three_var_combination((a, b, c, value_ranges, TARGET))
  163.             if res:
  164.                 solutions[(a, b, c)] = res
  165.  
  166.             if SHOW_PROGRESS and i % 10 == 0:
  167.                 print(f"\r三变量组合进度: {i}/{total_combinations} 组", end='')
  168.  
  169.     if SHOW_PROGRESS and not USE_MULTIPROCESSING:
  170.         print(f"\r三变量组合进度: {total_combinations}/{total_combinations} 组 - 完成")
  171.  
  172.     return solutions
  173.  
  174. def find_balanced_solutions(solutions, var_count, num=2):
  175.     """从所有解中筛选出最平衡的解"""
  176.     if var_count == 1 or not solutions:
  177.         return solutions
  178.  
  179.     balanced = []
  180.     for sol in solutions:
  181.         vars = sol[1::2]  # 获取解中的变量值
  182.         diff = max(vars) - min(vars)  # 计算变量之间的最大差值
  183.         balanced.append((diff, sol))
  184.  
  185.     # 按差值排序，返回差值最小的解
  186.     return [s for _, s in sorted(balanced, key=lambda x: x[0])[:num]]
  187.  
  188. def find_original_solutions(solutions, balanced_solutions, num=3):
  189.     """从剩余解中获取原始顺序的解"""
  190.     if not solutions:
  191.         return []
  192.  
  193.     remaining = [s for s in solutions if s not in balanced_solutions]
  194.     return remaining[:num]
  195.  
  196. def display_solutions(solutions_dict, var_count):
  197.     """优化的解显示函数"""
  198.     if not solutions_dict:
  199.         return
  200.  
  201.     print(f"\n找到 {len(solutions_dict)} 组{var_count}变量解：")
  202.  
  203.     for i, (coeffs, pair_solutions) in enumerate(sorted(solutions_dict.items()), 1):
  204.         balanced = find_balanced_solutions(pair_solutions, var_count)
  205.         original = find_original_solutions(pair_solutions, balanced)
  206.         all_display = balanced + original
  207.  
  208.         if var_count == 1:
  209.             a = coeffs
  210.             print(f"\n{i}. 组合: a={a} ({len(pair_solutions)} 个有效解)")
  211.         elif var_count == 2:
  212.             a, b = coeffs
  213.             print(f"\n{i}. 组合: a={a}, b={b} ({len(pair_solutions)} 个有效解)")
  214.         else:
  215.             a, b, c = coeffs
  216.             print(f"\n{i}. 组合: a={a}, b={b}, c={c} ({len(pair_solutions)} 个有效解)")
  217.  
  218.         for j, sol in enumerate(all_display, 1):
  219.             tag = "[平衡解]" if j <= len(balanced) else "[原始解]"
  220.  
  221.             if var_count == 1:
  222.                 a, x = sol
  223.                 print(f"  {j}. x={x}, a*x={a*x:.1f}, 总和={a*x:.1f} {tag}")
  224.             elif var_count == 2:
  225.                 a, x, b, y = sol
  226.                 print(f"  {j}. x={x}, y={y}, a*x={a*x:.1f}, b*y={b*y:.1f}, 总和={a*x + b*y:.1f} {tag}")
  227.             else:
  228.                 a, x, b, y, c, z = sol
  229.                 print(f"  {j}. x={x}, y={y}, z={z}, "
  230.                       f"a*x={a*x:.1f}, b*y={b*y:.1f}, c*z={c*z:.1f}, "
  231.                       f"总和={a*x + b*y + c*z:.1f} {tag}")
  232.  
  233. def run_with_timeout(func, args=(), kwargs=None, timeout=SOLVER_TIMEOUT):
  234.     """运行函数并设置超时限制"""
  235.     if kwargs is None:
  236.         kwargs = {}
  237.  
  238.     result = []
  239.     error = []
  240.  
  241.     def wrapper():
  242.         try:
  243.             result.append(func(*args, **kwargs))
  244.         except Exception as e:
  245.             error.append(e)
  246.  
  247.     thread = threading.Thread(target=wrapper)
  248.     thread.daemon = True
  249.     thread.start()
  250.     thread.join(timeout)
  251.  
  252.     if thread.is_alive():
  253.         print(f"警告: {func.__name__} 超时（{timeout}秒），跳过此方法")
  254.         return None
  255.  
  256.     if error:
  257.         raise error[0]
  258.  
  259.     return result[0]
  260.  
  261. def main():
  262.     print(f"目标值: {TARGET}")
  263.  
  264.     # 生成波动后的系数
  265.     FLUCTUATED_VALUES = [round(v - FLUCTUATION, 1) for v in BASE_VALUES]
  266.  
  267.     # 尝试基础系数
  268.     print(f"\n==== 尝试基础系数 ====")
  269.  
  270.     # 目标值255966 > 259000不成立，会按顺序尝试单、双、三变量解
  271.     base_solutions = {
  272.         'single': run_with_timeout(find_single_variable_solutions, args=(BASE_VALUES,)),
  273.         'two': run_with_timeout(find_two_variable_solutions, args=(BASE_VALUES,)),
  274.         'three': []
  275.     }
  276.  
  277.     has_solution = False
  278.  
  279.     # 显示单变量解
  280.     if base_solutions['single']:
  281.         has_solution = True
  282.         display_solutions({a: [sol] for a, sol in zip(BASE_VALUES, base_solutions['single']) if sol}, 1)
  283.  
  284.     # 显示双变量解
  285.     if base_solutions['two'] and len(base_solutions['two']) > 0:
  286.         has_solution = True
  287.         display_solutions(base_solutions['two'], 2)
  288.  
  289.     # 单变量和双变量都无解时，尝试三变量解
  290.     if not has_solution:
  291.         print(f"\n==== 单变量和双变量无解，尝试三变量解 ====")
  292.         base_solutions['three'] = run_with_timeout(find_three_variable_solutions, args=(BASE_VALUES,))
  293.  
  294.         if base_solutions['three'] and len(base_solutions['three']) > 0:
  295.             has_solution = True
  296.             display_solutions(base_solutions['three'], 3)
  297.  
  298.     if has_solution:
  299.         print(f"\n使用基础系数列表，共找到有效解")
  300.         return
  301.  
  302.     # 如果基础系数没有找到解，尝试波动系数
  303.     print(f"\n==== 尝试波动系数 ====")
  304.  
  305.     fluctuated_solutions = {
  306.         'single': run_with_timeout(find_single_variable_solutions, args=(FLUCTUATED_VALUES,)),
  307.         'two': run_with_timeout(find_two_variable_solutions, args=(FLUCTUATED_VALUES,)),
  308.         'three': []
  309.     }
  310.  
  311.     has_solution = False
  312.  
  313.     # 显示单变量解
  314.     if fluctuated_solutions['single']:
  315.         has_solution = True
  316.         display_solutions({a: [sol] for a, sol in zip(FLUCTUATED_VALUES, fluctuated_solutions['single']) if sol}, 1)
  317.  
  318.     # 显示双变量解
  319.     if fluctuated_solutions['two'] and len(fluctuated_solutions['two']) > 0:
  320.         has_solution = True
  321.         display_solutions(fluctuated_solutions['two'], 2)
  322.  
  323.     # 单变量和双变量都无解时，尝试三变量解
  324.     if not has_solution:
  325.         print(f"\n==== 单变量和双变量无解，尝试三变量解 ====")
  326.         fluctuated_solutions['three'] = run_with_timeout(find_three_variable_solutions, args=(FLUCTUATED_VALUES,))
  327.  
  328.         if fluctuated_solutions['three'] and len(fluctuated_solutions['three']) > 0:
  329.             has_solution = True
  330.             display_solutions(fluctuated_solutions['three'], 3)
  331.  
  332.     if has_solution:
  333.         print(f"\n使用波动系数列表，共找到有效解")
  334.         return
  335.  
  336.     # 如果所有系数集都没有找到解
  337.     print("\n没有找到符合条件的解，即使使用波动后的系数列表。")
  338.  
  339. if __name__ == "__main__":
  340.     start_time = time.time()
  341.     main()
  342.     print(f"\n总耗时: {time.time() - start_time:.2f}秒")
Success #stdin #stdout 0.07s 11756KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
目标值: 255966

==== 尝试基础系数 ====

找到 3 组2变量解：

1. 组合: a=41.5, b=59 (1 个有效解)
  1. x=3070, y=2179.0, a*x=127405.0, b*y=128561.0, 总和=255966.0 [平衡解]

2. 组合: a=68.5, b=91.5 (1 个有效解)
  1. x=1872, y=1396.0, a*x=128232.0, b*y=127734.0, 总和=255966.0 [平衡解]

3. 组合: a=74, b=74 (28 个有效解)
  1. x=1729, y=1730, a*x=127946.0, b*y=128020.0, 总和=255966.0 [平衡解]
  2. x=1730, y=1729, a*x=128020.0, b*y=127946.0, 总和=255966.0 [平衡解]
  3. x=1716, y=1743, a*x=126984.0, b*y=128982.0, 总和=255966.0 [原始解]
  4. x=1717, y=1742, a*x=127058.0, b*y=128908.0, 总和=255966.0 [原始解]
  5. x=1718, y=1741, a*x=127132.0, b*y=128834.0, 总和=255966.0 [原始解]

使用基础系数列表，共找到有效解

总耗时: 0.01秒
https://ideone.com/Gu3pyi
language:
Python 3 nbc (python 3.7.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!