fork download 
  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 = 122360# 目标值
  10. BASE_VALUES = [38.5,44,61,70.5,75.5,93] # 基础系数列表
  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.09s 11692KB
comments (?)
stdin 
Standard input is empty
stdout 
目标值: 122360

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

找到 11 组2变量解：

1. 组合: a=38.5, b=61 (9 个有效解)
  1. x=1204, y=1246.0, a*x=46354.0, b*y=76006.0, 总和=122360.0 [平衡解]
  2. x=1570, y=1015.0, a*x=60445.0, b*y=61915.0, 总和=122360.0 [平衡解]
  3. x=106, y=1939.0, a*x=4081.0, b*y=118279.0, 总和=122360.0 [原始解]
  4. x=472, y=1708.0, a*x=18172.0, b*y=104188.0, 总和=122360.0 [原始解]
  5. x=838, y=1477.0, a*x=32263.0, b*y=90097.0, 总和=122360.0 [原始解]

2. 组合: a=38.5, b=75.5 (7 个有效解)
  1. x=1174, y=1022.0, a*x=45199.0, b*y=77161.0, 总和=122360.0 [平衡解]
  2. x=721, y=1253.0, a*x=27758.5, b*y=94601.5, 总和=122360.0 [平衡解]
  3. x=268, y=1484.0, a*x=10318.0, b*y=112042.0, 总和=122360.0 [原始解]
  4. x=1627, y=791.0, a*x=62639.5, b*y=59720.5, 总和=122360.0 [原始解]
  5. x=2080, y=560.0, a*x=80080.0, b*y=42280.0, 总和=122360.0 [原始解]

3. 组合: a=44, b=61 (23 个有效解)
  1. x=1145, y=1180, a*x=50380.0, b*y=71980.0, 总和=122360.0 [平衡解]
  2. x=1267, y=1092, a*x=55748.0, b*y=66612.0, 总和=122360.0 [平衡解]
  3. x=47, y=1972, a*x=2068.0, b*y=120292.0, 总和=122360.0 [原始解]
  4. x=169, y=1884, a*x=7436.0, b*y=114924.0, 总和=122360.0 [原始解]
  5. x=291, y=1796, a*x=12804.0, b*y=109556.0, 总和=122360.0 [原始解]

4. 组合: a=44, b=70.5 (10 个有效解)
  1. x=1153, y=1016.0, a*x=50732.0, b*y=71628.0, 总和=122360.0 [平衡解]
  2. x=871, y=1192.0, a*x=38324.0, b*y=84036.0, 总和=122360.0 [平衡解]
  3. x=25, y=1720.0, a*x=1100.0, b*y=121260.0, 总和=122360.0 [原始解]
  4. x=307, y=1544.0, a*x=13508.0, b*y=108852.0, 总和=122360.0 [原始解]
  5. x=589, y=1368.0, a*x=25916.0, b*y=96444.0, 总和=122360.0 [原始解]

5. 组合: a=44, b=75.5 (9 个有效解)
  1. x=1065, y=1000.0, a*x=46860.0, b*y=75500.0, 总和=122360.0 [平衡解]
  2. x=763, y=1176.0, a*x=33572.0, b*y=88788.0, 总和=122360.0 [平衡解]
  3. x=159, y=1528.0, a*x=6996.0, b*y=115364.0, 总和=122360.0 [原始解]
  4. x=461, y=1352.0, a*x=20284.0, b*y=102076.0, 总和=122360.0 [原始解]
  5. x=1367, y=824.0, a*x=60148.0, b*y=62212.0, 总和=122360.0 [原始解]

6. 组合: a=44, b=93 (15 个有效解)
  1. x=811, y=932, a*x=35684.0, b*y=86676.0, 总和=122360.0 [平衡解]
  2. x=997, y=844, a*x=43868.0, b*y=78492.0, 总和=122360.0 [平衡解]
  3. x=67, y=1284, a*x=2948.0, b*y=119412.0, 总和=122360.0 [原始解]
  4. x=253, y=1196, a*x=11132.0, b*y=111228.0, 总和=122360.0 [原始解]
  5. x=439, y=1108, a*x=19316.0, b*y=103044.0, 总和=122360.0 [原始解]

7. 组合: a=61, b=70.5 (7 个有效解)
  1. x=797, y=1046.0, a*x=48617.0, b*y=73743.0, 总和=122360.0 [平衡解]
  2. x=1079, y=802.0, a*x=65819.0, b*y=56541.0, 总和=122360.0 [平衡解]
  3. x=233, y=1534.0, a*x=14213.0, b*y=108147.0, 总和=122360.0 [原始解]
  4. x=515, y=1290.0, a*x=31415.0, b*y=90945.0, 总和=122360.0 [原始解]
  5. x=1361, y=558.0, a*x=83021.0, b*y=39339.0, 总和=122360.0 [原始解]

8. 组合: a=61, b=75.5 (7 个有效解)
  1. x=939, y=862.0, a*x=57279.0, b*y=65081.0, 总和=122360.0 [平衡解]
  2. x=637, y=1106.0, a*x=38857.0, b*y=83503.0, 总和=122360.0 [平衡解]
  3. x=33, y=1594.0, a*x=2013.0, b*y=120347.0, 总和=122360.0 [原始解]
  4. x=335, y=1350.0, a*x=20435.0, b*y=101925.0, 总和=122360.0 [原始解]
  5. x=1241, y=618.0, a*x=75701.0, b*y=46659.0, 总和=122360.0 [原始解]

9. 组合: a=61, b=93 (11 个有效解)
  1. x=803, y=789, a*x=48983.0, b*y=73377.0, 总和=122360.0 [平衡解]
  2. x=617, y=911, a*x=37637.0, b*y=84723.0, 总和=122360.0 [平衡解]
  3. x=59, y=1277, a*x=3599.0, b*y=118761.0, 总和=122360.0 [原始解]
  4. x=245, y=1155, a*x=14945.0, b*y=107415.0, 总和=122360.0 [原始解]
  5. x=431, y=1033, a*x=26291.0, b*y=96069.0, 总和=122360.0 [原始解]

10. 组合: a=70.5, b=75.5 (11 个有效解)
  1. x=896, y=784.0, a*x=63168.0, b*y=59192.0, 总和=122360.0 [平衡解]
  2. x=745, y=925.0, a*x=52522.5, b*y=69837.5, 总和=122360.0 [平衡解]
  3. x=141, y=1489.0, a*x=9940.5, b*y=112419.5, 总和=122360.0 [原始解]
  4. x=292, y=1348.0, a*x=20586.0, b*y=101774.0, 总和=122360.0 [原始解]
  5. x=443, y=1207.0, a*x=31231.5, b*y=91128.5, 总和=122360.0 [原始解]

11. 组合: a=75.5, b=93 (9 个有效解)
  1. x=634, y=801.0, a*x=47867.0, b*y=74493.0, 总和=122360.0 [平衡解]
  2. x=820, y=650.0, a*x=61910.0, b*y=60450.0, 总和=122360.0 [平衡解]
  3. x=76, y=1254.0, a*x=5738.0, b*y=116622.0, 总和=122360.0 [原始解]
  4. x=262, y=1103.0, a*x=19781.0, b*y=102579.0, 总和=122360.0 [原始解]
  5. x=448, y=952.0, a*x=33824.0, b*y=88536.0, 总和=122360.0 [原始解]

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

总耗时: 0.02秒
https://ideone.com/qgBU73
language:
Python 3 nbc (python 3.7.3)
created:
9 days 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!