fork download
copy 
  1. import itertools
  2.  
  3. # --------------------------
  4. # 配置参数 - 可根据需求修改
  5. # --------------------------
  6. CONFIG = {
  7.     # 基础系数列表
  8.     'base_coefficients': [36.5, 41.5, 59, 68.5, 74, 91.5] ,
  9.     # 目标值
  10.     'target':298600,
  11.     # 单个系数乘积的最大限制
  12.     'max_product': 129000,
  13.     # 最大变量数量（根据问题特点固定为3以提高速度）
  14.     'max_vars': 3,
  15.     # 目标值阈值（超过此值使用3变量）
  16.     'target_threshold': 259000,
  17.     # 减少波动范围以加快计算
  18.     'fluctuation_range': [i * 0.5 for i in range(-2, 3)],  # ±1.0范围，步长0.5
  19.     # 限制解的数量以避免不必要计算
  20.     'max_solutions_per_combo': 20,
  21.     # 最终筛选的最佳解数量
  22.     'max_best_solutions': 4,
  23.     # 平衡解的数量
  24.     'balanced_solutions_count': 2
  25. }
  26.  
  27. def find_solutions(config):
  28.     """优化版：采用数学推导和剪枝策略加速求解"""
  29.     solutions = []
  30.     # 提取配置参数
  31.     target = config['target']
  32.     base_coefficients = config['base_coefficients']
  33.     max_product = config['max_product']
  34.     max_vars = config['max_vars']
  35.     target_threshold = config['target_threshold']
  36.     fluctuations = config['fluctuation_range']
  37.     max_solutions = config['max_solutions_per_combo']
  38.  
  39.     # 根据目标值确定变量数量（直接使用3变量以加速）
  40.     num_vars = 3 if target > target_threshold else min(3, max_vars)
  41.  
  42.     # 对系数排序，优先尝试大系数组合（减少迭代次数）
  43.     coefficients = sorted(base_coefficients, reverse=True)
  44.  
  45.     # 只处理3变量情况，这是最可能找到解的组合且效率最高
  46.     # 生成系数组合（只取较大的系数，小系数组合可能性低）
  47.     start_idx = 0
  48.     end_idx = min(5, len(coefficients))  # 只取前5个较大的系数组合
  49.     for combo in itertools.combinations(coefficients[start_idx:end_idx], num_vars):
  50.         # 计算每个系数的可能值范围（使用更严格的范围）
  51.         ranges = []
  52.         valid = True
  53.         for coeff in combo:
  54.             if coeff <= 0:
  55.                 valid = False
  56.                 break
  57.             # 计算更精确的取值范围
  58.             min_val = max(1, int((target - (max_product * (num_vars - 1))) / coeff))
  59.             max_val = min(int(max_product / coeff), int(target / coeff))
  60.             if min_val > max_val:
  61.                 valid = False
  62.                 break
  63.             ranges.append(range(min_val, max_val + 1))
  64.  
  65.         if not valid:
  66.             continue
  67.  
  68.         # 优化搜索顺序：先处理中间变量，减少外层循环次数
  69.         # 对于3变量，固定前两个变量的范围，计算第三个变量
  70.         coeff1, coeff2, coeff3 = combo
  71.         range1, range2, range3 = ranges
  72.  
  73.         # 限制第一个变量的范围，只取中间部分（加速）
  74.         step = max(1, len(range1) // 20)  # 跳步采样，减少50倍计算量
  75.         for x in range1[::step]:
  76.             product1 = coeff1 * x
  77.             remaining1 = target - product1
  78.  
  79.             if remaining1 <= 0:
  80.                 continue
  81.  
  82.             # 计算第二个变量的有效范围
  83.             min_y = max(range2.start, int((remaining1 - (coeff3 * range3.stop)) / coeff2))
  84.             max_y = min(range2.stop - 1, int((remaining1 - (coeff3 * range3.start)) / coeff2))
  85.  
  86.             if min_y > max_y:
  87.                 continue
  88.  
  89.             # 对第二个变量也进行跳步采样
  90.             y_step = max(1, (max_y - min_y) // 20)
  91.             for y in range(min_y, max_y + 1, y_step):
  92.                 product2 = coeff2 * y
  93.                 remaining2 = remaining1 - product2
  94.  
  95.                 if remaining2 <= 0:
  96.                     continue
  97.  
  98.                 # 直接计算第三个变量，无需循环
  99.                 if remaining2 % coeff3 == 0:
  100.                     z = int(remaining2 / coeff3)
  101.                     if z in range3:
  102.                         product3 = coeff3 * z
  103.                         # 验证总和
  104.                         if abs(product1 + product2 + product3 - target) < 1e-6:
  105.                             solutions.append({
  106.                                 'coefficients': combo,
  107.                                 'values': (x, y, z),
  108.                                 'total': target,
  109.                                 'num_vars': num_vars,
  110.                                 'products': (product1, product2, product3)
  111.                             })
  112.                             # 找到足够解后提前退出
  113.                             if len(solutions) >= max_solutions:
  114.                                 return solutions
  115.  
  116.     # 如果没有找到解，再尝试系数波动（简化版）
  117.     if not solutions and len(fluctuations) > 0:
  118.         for combo in itertools.combinations(coefficients[:4], num_vars):  # 只取前4个大系数
  119.             # 生成波动组合（减少波动数量）
  120.             fluctuated_combos = []
  121.             for i in range(num_vars):
  122.                 if i == 0:  # 只对第一个系数进行波动
  123.                     fluctuated_combos.append([combo[i] + d for d in fluctuations])
  124.                 else:
  125.                     fluctuated_combos.append([combo[i]])  # 其他系数不波动
  126.  
  127.             for fluctuated_combo in itertools.product(*fluctuated_combos):
  128.                 if any(c <= 0 for c in fluctuated_combo):
  129.                     continue
  130.  
  131.                 # 计算变量范围
  132.                 ranges = []
  133.                 valid = True
  134.                 for coeff in fluctuated_combo:
  135.                     min_val = max(1, int((target - (max_product * (num_vars - 1))) / coeff))
  136.                     max_val = min(int(max_product / coeff), int(target / coeff))
  137.                     if min_val > max_val:
  138.                         valid = False
  139.                         break
  140.                     ranges.append(range(min_val, max_val + 1))
  141.  
  142.                 if not valid:
  143.                     continue
  144.  
  145.                 # 同样的优化搜索方式
  146.                 coeff1, coeff2, coeff3 = fluctuated_combo
  147.                 range1, range2, range3 = ranges
  148.  
  149.                 step = max(1, len(range1) // 20)
  150.                 for x in range1[::step]:
  151.                     product1 = coeff1 * x
  152.                     remaining1 = target - product1
  153.                     if remaining1 <= 0:
  154.                         continue
  155.  
  156.                     min_y = max(range2.start, int((remaining1 - (coeff3 * range3.stop)) / coeff2))
  157.                     max_y = min(range2.stop - 1, int((remaining1 - (coeff3 * range3.start)) / coeff2))
  158.                     if min_y > max_y:
  159.                         continue
  160.  
  161.                     y_step = max(1, (max_y - min_y) // 20)
  162.                     for y in range(min_y, max_y + 1, y_step):
  163.                         product2 = coeff2 * y
  164.                         remaining2 = remaining1 - product2
  165.                         if remaining2 <= 0:
  166.                             continue
  167.  
  168.                         z = remaining2 / coeff3
  169.                         if abs(z - round(z)) < 1e-6:
  170.                             z = int(round(z))
  171.                             if z in range3:
  172.                                 product3 = coeff3 * z
  173.                                 if abs(product1 + product2 + product3 - target) < 1e-6:
  174.                                     solutions.append({
  175.                                         'coefficients': fluctuated_combo,
  176.                                         'values': (x, y, z),
  177.                                         'total': target,
  178.                                         'num_vars': num_vars,
  179.                                         'fluctuated': True,
  180.                                         'products': (product1, product2, product3)
  181.                                     })
  182.                                     if len(solutions) >= max_solutions:
  183.                                         return solutions
  184.  
  185.     return solutions
  186.  
  187. def select_best_solutions(solutions, config):
  188.     """简化版筛选函数，提高速度"""
  189.     if not solutions:
  190.         return []
  191.  
  192.     # 提取配置参数
  193.     max_best = config['max_best_solutions']
  194.     balanced_count = config['balanced_solutions_count']
  195.  
  196.     # 计算每个解的平衡分数（使用简化计算）
  197.     for sol in solutions:
  198.         # 使用乘积的方差作为平衡分数（值越小越平衡）
  199.         p1, p2, p3 = sol['products']
  200.         mean = (p1 + p2 + p3) / 3
  201.         sol['balance_score'] = (abs(p1 - mean) + abs(p2 - mean) + abs(p3 - mean)) / 3  # 改用绝对值和，更快
  202.  
  203.     # 按平衡分数排序
  204.     solutions.sort(key=lambda x: x['balance_score'])
  205.  
  206.     # 选择最佳解
  207.     result = []
  208.     # 先选平衡解
  209.     result.extend(solutions[:balanced_count])
  210.     # 再选普通解
  211.     result.extend(solutions[balanced_count:balanced_count + (max_best - balanced_count)])
  212.  
  213.     return result[:max_best]
  214.  
  215. def main():
  216.     # 查找所有可能的解（优化版，速度更快）
  217.     all_solutions = find_solutions(CONFIG)
  218.  
  219.     if not all_solutions:
  220.         print("未找到任何解")
  221.         return
  222.  
  223.     # 选择最佳解
  224.     best_solutions = select_best_solutions(all_solutions, CONFIG)
  225.  
  226.     # 处理解，将系数按从小到大排序
  227.     processed_solutions = []
  228.     for sol in best_solutions:
  229.         # 组合系数和值并排序
  230.         combined = list(zip(sol['coefficients'], sol['values'], sol['products']))
  231.         combined_sorted = sorted(combined, key=lambda x: x[0])  # 按系数排序
  232.         sorted_coeffs, sorted_values, sorted_products = zip(*combined_sorted)
  233.  
  234.         processed_sol = sol.copy()
  235.         processed_sol['sorted_coefficients'] = sorted_coeffs
  236.         processed_sol['sorted_values'] = sorted_values
  237.         processed_sol['sorted_products'] = sorted_products
  238.         processed_sol['is_balanced'] = len(processed_solutions) < CONFIG['balanced_solutions_count']
  239.         processed_solutions.append(processed_sol)
  240.  
  241.     # 按排序后的系数组合分组显示结果
  242.     combo_groups = {}
  243.     for sol in processed_solutions:
  244.         combo_key = sol['sorted_coefficients']
  245.         if combo_key not in combo_groups:
  246.             combo_groups[combo_key] = []
  247.         combo_groups[combo_key].append(sol)
  248.  
  249.     # 显示每个组合及其解
  250.     for combo, solutions in combo_groups.items():
  251.         coeff_labels = [chr(97 + i) for i in range(len(combo))]  # a, b, c...
  252.         combo_str = ", ".join([f"{label}={coeff:.1f}" for label, coeff in zip(coeff_labels, combo)])
  253.         print(f"组合: {combo_str} ({len(solutions)} 个有效解)")
  254.  
  255.         for i, sol in enumerate(solutions, 1):
  256.             # 第一行：未知数
  257.             values_str = ", ".join([f"{chr(120 + j)}={val}" for j, val in enumerate(sol['sorted_values'])])
  258.             print(f"  {i}. {values_str},")
  259.  
  260.             # 第二行：乘积和总和
  261.             products_str = ", ".join([f"{label}*{chr(120 + j)}={p:.1f}" 
  262.                                     for j, (label, p) in enumerate(zip(coeff_labels, sol['sorted_products']))])
  263.             balanced_tag = " [平衡解]" if sol['is_balanced'] else ""
  264.             print(f"  {products_str}, 总和 = {sol['total']:.1f}{balanced_tag}")
  265.  
  266.         print()
  267.  
  268. if __name__ == "__main__":
  269.     main()
  270.  
Success #stdin #stdout 0.04s 9736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
组合: a=68.5, b=74.0, c=91.5 (1 个有效解)
  1. x=1603, y=1410, z=923,
  a*x=109805.5, b*y=104340.0, c*z=84454.5, 总和 = 298600.0 [平衡解]

组合: a=41.5, b=74.0, c=91.5 (1 个有效解)
  1. x=2489, y=1498, z=923,
  a*x=103293.5, b*y=110852.0, c*z=84454.5, 总和 = 298600.0 [平衡解]

组合: a=41.5, b=59.0, c=91.5 (2 个有效解)
  1. x=2171, y=1507, z=1307,
  a*x=90096.5, b*y=88913.0, c*z=119590.5, 总和 = 298600.0
  2. x=2797, y=1290, z=1163,
  a*x=116075.5, b*y=76110.0, c*z=106414.5, 总和 = 298600.0
https://ideone.com/8KW2bP
language:
Python 3 nbc (python 3.7.3)
created:
2 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!