fork download 
  1. import itertools
  2. CONFIG = {
  3.     # 基础系数列表
  4.     'base_coefficients': [38.5, 44, 61, 70.5, 75.5, 93],
  5.     # 目标值
  6.     'target': 268668,
  7.     # 单个系数乘积的最大限制
  8.     'max_product': 129000,
  9.     # 最大变量数量
  10.     'max_vars': 4,
  11.     # 目标值阈值（超过此值使用3-4变量）
  12.     'target_threshold': 259000,
  13.     # 系数波动范围（±1.0，步长0.1）
  14.     'fluctuation_range': [i * 0.1 for i in range(-10, 11)],
  15.     # 每个组合的最大解数量（用于提前终止）
  16.     'max_solutions_per_combo': 100,
  17.     # 最终筛选的最佳解数量（平衡解+普通解）
  18.     'max_best_solutions': 4,
  19.     # 平衡解的数量
  20.     'balanced_solutions_count': 2
  21. }
  22.  
  23. def find_solutions(config):
  24.     """寻找目标值的系数组合解，采用高效的搜索策略"""
  25.     solutions = []
  26.     # 提取配置参数
  27.     target = config['target']
  28.     base_coefficients = config['base_coefficients']
  29.     max_product = config['max_product']
  30.     max_vars = config['max_vars']
  31.     target_threshold = config['target_threshold']
  32.     fluctuations = config['fluctuation_range']
  33.     max_solutions = config['max_solutions_per_combo']
  34.  
  35.     # 对系数排序，优先尝试大系数组合，减少迭代次数
  36.     coefficients = sorted(base_coefficients, reverse=True)
  37.  
  38.     # 根据目标值确定变量数量范围
  39.     start_vars, end_vars = (3, 4) if target > target_threshold else (1, max_vars)
  40.  
  41.     # 按变量数量递增搜索（优先少变量解）
  42.     for num_vars in range(start_vars, end_vars + 1):
  43.         # 生成不重复的系数组合
  44.         for combo in itertools.combinations(coefficients, num_vars):
  45.             # 计算每个系数的最大可能值
  46.             max_values = []
  47.             valid = True
  48.             for coeff in combo:
  49.                 if coeff <= 0:
  50.                     valid = False
  51.                     break
  52.                 # 单个系数乘积不超过最大限制
  53.                 max_val = int(min(max_product / coeff, target / coeff)) + 1
  54.                 if max_val <= 0:
  55.                     valid = False
  56.                     break
  57.                 max_values.append(max_val)
  58.  
  59.             if not valid:
  60.                 continue
  61.  
  62.             # 智能搜索策略：前n-1个变量遍历，最后一个变量反推
  63.             if num_vars == 1:
  64.                 # 单变量情况
  65.                 coeff = combo[0]
  66.                 if target % coeff == 0:
  67.                     val = int(target / coeff)
  68.                     if 1 <= val <= max_values[0]:
  69.                         solutions.append({
  70.                             'coefficients': combo,
  71.                             'values': (val,),
  72.                             'total': target,
  73.                             'num_vars': num_vars
  74.                         })
  75.             else:
  76.                 # 多变量情况
  77.                 first_coeffs = combo[:-1]
  78.                 last_coeff = combo[-1]
  79.                 first_max_values = max_values[:-1]
  80.                 last_max_val = max_values[-1]
  81.  
  82.                 # 生成前n-1个变量的所有组合
  83.                 for first_values in itertools.product(*[range(1, mv+1) for mv in first_max_values]):
  84.                     # 计算已用总和
  85.                     used = sum(c * v for c, v in zip(first_coeffs, first_values))
  86.                     remaining = target - used
  87.  
  88.                     if remaining <= 0:
  89.                         continue
  90.  
  91.                     if remaining % last_coeff == 0:
  92.                         last_val = int(remaining / last_coeff)
  93.                         if 1 <= last_val <= last_max_val:
  94.                             # 验证总乘积是否符合要求
  95.                             products = [c * v for c, v in zip(first_coeffs, first_values)] + [last_coeff * last_val]
  96.                             if all(p <= max_product for p in products):
  97.                                 values = first_values + (last_val,)
  98.                                 solutions.append({
  99.                                     'coefficients': combo,
  100.                                     'values': values,
  101.                                     'total': target,
  102.                                     'num_vars': num_vars
  103.                                 })
  104.  
  105.             # 找到足够解后提前退出
  106.             if len(solutions) >= max_solutions:
  107.                 break
  108.  
  109.         if len(solutions) >= max_solutions:
  110.             break
  111.  
  112.     # 如果没有找到解，尝试系数波动
  113.     if not solutions:
  114.         for num_vars in range(start_vars, end_vars + 1):
  115.             for combo in itertools.combinations(coefficients, num_vars):
  116.                 # 生成所有可能的波动组合
  117.                 fluctuated_coeffs_list = []
  118.                 for coeff in combo:
  119.                     fluctuated_coeffs_list.append([coeff + d for d in fluctuations])
  120.  
  121.                 # 尝试每个波动后的系数组合
  122.                 for fluctuated_combo in itertools.product(*fluctuated_coeffs_list):
  123.                     if any(c <= 0 for c in fluctuated_combo):
  124.                         continue
  125.  
  126.                     # 计算每个系数的最大可能值
  127.                     max_values = []
  128.                     valid = True
  129.                     for coeff in fluctuated_combo:
  130.                         max_val = int(min(max_product / coeff, target / coeff)) + 1
  131.                         if max_val <= 0:
  132.                             valid = False
  133.                             break
  134.                         max_values.append(max_val)
  135.  
  136.                     if not valid:
  137.                         continue
  138.  
  139.                     # 使用同样的智能搜索策略
  140.                     if num_vars == 1:
  141.                         coeff = fluctuated_combo[0]
  142.                         if abs(target % coeff) < 1e-6:  # 考虑浮点误差
  143.                             val = int(round(target / coeff))
  144.                             if 1 <= val <= max_values[0] and abs(coeff * val - target) < 1e-6:
  145.                                 solutions.append({
  146.                                     'coefficients': fluctuated_combo,
  147.                                     'values': (val,),
  148.                                     'total': target,
  149.                                     'num_vars': num_vars,
  150.                                     'fluctuated': True
  151.                                 })
  152.                     else:
  153.                         first_coeffs = fluctuated_combo[:-1]
  154.                         last_coeff = fluctuated_combo[-1]
  155.                         first_max_values = max_values[:-1]
  156.                         last_max_val = max_values[-1]
  157.  
  158.                         for first_values in itertools.product(*[range(1, mv+1) for mv in first_max_values]):
  159.                             used = sum(c * v for c, v in zip(first_coeffs, first_values))
  160.                             remaining = target - used
  161.  
  162.                             if remaining <= 0:
  163.                                 continue
  164.  
  165.                             # 处理浮点除法
  166.                             last_val = remaining / last_coeff
  167.                             if abs(last_val - round(last_val)) < 1e-6:
  168.                                 last_val = int(round(last_val))
  169.                                 if 1 <= last_val <= last_max_val:
  170.                                     # 验证总乘积和总和
  171.                                     products = [c * v for c, v in zip(first_coeffs, first_values)] + [last_coeff * last_val]
  172.                                     if all(p <= max_product for p in products):
  173.                                         total = sum(c * v for c, v in zip(fluctuated_combo, first_values + (last_val,)))
  174.                                         if abs(total - target) < 1e-6:
  175.                                             values = first_values + (last_val,)
  176.                                             solutions.append({
  177.                                                 'coefficients': fluctuated_combo,
  178.                                                 'values': values,
  179.                                                 'total': total,
  180.                                                 'num_vars': num_vars,
  181.                                                 'fluctuated': True
  182.                                             })
  183.  
  184.             if len(solutions) >= max_solutions:
  185.                 break
  186.  
  187.     # 如果仍然没有找到解，取消最大乘积限制
  188.     if not solutions:
  189.         for num_vars in range(start_vars, end_vars + 1):
  190.             for combo in itertools.combinations(coefficients, num_vars):
  191.                 # 不限制最大乘积，但设置合理范围
  192.                 max_values = [int(target / coeff) + 100 for coeff in combo if coeff > 0]
  193.                 if any(mv <= 0 for mv in max_values):
  194.                     continue
  195.  
  196.                 # 使用相同的智能搜索策略
  197.                 if num_vars == 1:
  198.                     coeff = combo[0]
  199.                     if target % coeff == 0:
  200.                         val = int(target / coeff)
  201.                         if val > 0:
  202.                             solutions.append({
  203.                                 'coefficients': combo,
  204.                                 'values': (val,),
  205.                                 'total': target,
  206.                                 'num_vars': num_vars,
  207.                                 'unrestricted': True
  208.                             })
  209.                 else:
  210.                     first_coeffs = combo[:-1]
  211.                     last_coeff = combo[-1]
  212.                     first_max_values = max_values[:-1]
  213.                     last_max_val = max_values[-1]
  214.  
  215.                     for first_values in itertools.product(*[range(1, mv+1) for mv in first_max_values]):
  216.                         used = sum(c * v for c, v in zip(first_coeffs, first_values))
  217.                         remaining = target - used
  218.  
  219.                         if remaining <= 0:
  220.                             continue
  221.  
  222.                         if remaining % last_coeff == 0:
  223.                             last_val = int(remaining / last_coeff)
  224.                             if 1 <= last_val <= last_max_val:
  225.                                 values = first_values + (last_val,)
  226.                                 solutions.append({
  227.                                     'coefficients': combo,
  228.                                     'values': values,
  229.                                     'total': target,
  230.                                     'num_vars': num_vars,
  231.                                     'unrestricted': True
  232.                                 })
  233.  
  234.             if len(solutions) >= max_solutions:
  235.                 break
  236.  
  237.     return solutions
  238.  
  239. def select_best_solutions(solutions, config):
  240.     """筛选最佳解，平衡解和普通解按配置参数设置"""
  241.     if not solutions:
  242.         return []
  243.  
  244.     # 提取配置参数
  245.     max_best = config['max_best_solutions']
  246.     balanced_count = config['balanced_solutions_count']
  247.  
  248.     # 按变量数量排序，优先选择变量少的解
  249.     solutions.sort(key=lambda x: x['num_vars'])
  250.  
  251.     # 计算每个解的平衡分数（各乘积的标准差）
  252.     for sol in solutions:
  253.         products = [c * v for c, v in zip(sol['coefficients'], sol['values'])]
  254.         mean = sum(products) / len(products)
  255.         std = (sum((p - mean) **2 for p in products) / len(products))** 0.5
  256.         sol['balance_score'] = std
  257.  
  258.     # 先按变量数量分组
  259.     var_groups = {}
  260.     for sol in solutions:
  261.         key = sol['num_vars']
  262.         if key not in var_groups:
  263.             var_groups[key] = []
  264.         var_groups[key].append(sol)
  265.  
  266.     # 优先从变量最少的组中选择解
  267.     result = []
  268.     balanced_selected = 0
  269.     others_selected = 0
  270.  
  271.     # 按变量数量升序处理各组
  272.     for var_count in sorted(var_groups.keys()):
  273.         group = sorted(var_groups[var_count], key=lambda x: x['balance_score'])
  274.  
  275.         # 先选平衡解
  276.         for sol in group:
  277.             if balanced_selected < balanced_count:
  278.                 sol['is_balanced'] = True
  279.                 result.append(sol)
  280.                 balanced_selected += 1
  281.             else:
  282.                 break
  283.  
  284.         # 再选普通解
  285.         needed_others = max_best - balanced_count
  286.         for sol in group[balanced_selected:]:
  287.             if others_selected < needed_others:
  288.                 sol['is_balanced'] = False
  289.                 result.append(sol)
  290.                 others_selected += 1
  291.             else:
  292.                 break
  293.  
  294.         # 选够指定数量的解则停止
  295.         if len(result) >= max_best:
  296.             break
  297.  
  298.     return result[:max_best]
  299.  
  300. def main():
  301.     # 查找所有可能的解
  302.     all_solutions = find_solutions(CONFIG)
  303.  
  304.     if not all_solutions:
  305.         print("未找到任何解")
  306.         return
  307.  
  308.     # 选择最佳解
  309.     best_solutions = select_best_solutions(all_solutions, CONFIG)
  310.  
  311.     # 按系数组合分组显示结果
  312.     combo_groups = {}
  313.     for sol in best_solutions:
  314.         # 使用系数元组作为键，确保相同组合分到一组
  315.         combo_key = tuple(sol['coefficients'])
  316.         if combo_key not in combo_groups:
  317.             combo_groups[combo_key] = []
  318.         combo_groups[combo_key].append(sol)
  319.  
  320.     # 显示每个组合及其解
  321.     for combo, solutions in combo_groups.items():
  322.         # 生成系数字母标签 (a, b, c, d...)
  323.         coeff_labels = [chr(97 + i) for i in range(len(combo))]
  324.         # 构建组合字符串 (如 "a=41.5, b=59")
  325.         combo_str = ", ".join([f"{label}={coeff:.1f}" for label, coeff in zip(coeff_labels, combo)])
  326.         # 显示组合信息
  327.         print(f"组合: {combo_str} ({len(solutions)} 个有效解)")
  328.  
  329.         # 显示该组合下的所有解
  330.         for i, sol in enumerate(solutions, 1):
  331.             # 构建未知数字符串 (如 "x=3070, y=2179")
  332.             values_str = ", ".join([f"{chr(120 + j)}={val}" for j, val in enumerate(sol['values'])])
  333.             # 构建乘积字符串 (如 "a*x=127405.0, b*y=128561.0")
  334.             products = [c * v for c, v in zip(sol['coefficients'], sol['values'])]
  335.             products_str = ", ".join([f"{label}*{chr(120 + j)}={p:.1f}" 
  336.                                      for j, (label, p) in enumerate(zip(coeff_labels, products))])
  337.             # 构建平衡解标记
  338.             balanced_tag = " [平衡解]" if sol['is_balanced'] else ""
  339.             # 显示解信息
  340.             print(f"  {i}. {values_str}, {products_str}, 总和={sol['total']:.1f}{balanced_tag}")
  341.         print()  # 组合之间空一行
  342.  
  343. if __name__ == "__main__":
  344.     main()
  345.  
Success #stdin #stdout 3.08s 12320KB
comments (?)
stdin 
Standard input is empty
stdout 
组合: a=93.0, b=75.5, c=70.5 (4 个有效解)
  1. x=957, y=1191, z=1273, a*x=89001.0, b*y=89920.5, c*z=89746.5, 总和=268668.0 [平衡解]
  2. x=959, y=1182, z=1280, a*x=89187.0, b*y=89241.0, c*z=90240.0, 总和=268668.0 [平衡解]
  3. x=955, y=1200, z=1266, a*x=88815.0, b*y=90600.0, c*z=89253.0, 总和=268668.0
  4. x=974, y=1185, z=1257, a*x=90582.0, b*y=89467.5, c*z=88618.5, 总和=268668.0
https://ideone.com/4LF91o
language:
Python 3 nbc (python 3.7.3)
created:
10 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!