E96系抵抗値の組み合わせを計算するコード

resistor_combination.py

import math
import copy

resistor_e96 = [
    1.00, 1.02, 1.05, 1.07, 1.10, 1.13, 1.15, 1.18, 1.21, 1.24, 1.27, 1.30, 1.33, 1.37, 1.40, 1.43, 1.47, 1.50, 1.54, 1.58, 1.62, 1.65, 1.69, 1.74, 1.78, 1.82, 1.87, 1.91, 1.96, 2.00, 2.05, 2.10, 2.15, 2.21, 2.26, 2.32, 2.37, 2.43, 2.49, 2.55, 2.61, 2.67, 2.74, 2.80, 2.87, 2.94, 3.01, 3.09, 3.16, 3.24, 3.32, 3.40, 3.48, 3.57, 3.65, 3.74, 3.83, 3.92, 4.02, 4.12, 4.22, 4.32, 4.42, 4.53, 4.64, 4.75, 4.87, 4.99, 5.11, 5.23, 5.36, 5.49, 5.62, 5.76, 5.90, 6.04, 6.19, 6.34, 6.49, 6.65, 6.81, 6.98, 7.15, 7.32, 7.50, 7.68, 7.87, 8.06, 8.25, 8.45, 8.66, 8.87, 9.09, 9.31, 9.53, 9.76
]


# dpを使うために整数にする
SHIFT = 100
resistor_values = [0]
for i in [x * SHIFT for x in [1.0, 10.0, 100.0, 1000.0]]:
    resistor_values += [int(i * x) for x in resistor_e96]

target = int(1.282 * 1000 * SHIFT)
# target = 1000 # mOhm
limit = 3


def dp_find(dp, target, resistor_values):
    if dp[target] != []:
        return dp[target]

    # resistor_values から target を超えない値と超える値を取り出す
    idx = len(resistor_values) // 2
    candidate = copy.copy(resistor_values)
    
    while 2 < len(candidate):
        # 2分探索
        if candidate[idx] < target:
            candidate = candidate[idx:]
        elif candidate[idx] == target:
            candidate = [candidate[idx]]
        else:
            candidate = candidate[:idx + 1]
        idx = int(idx / 2 + 0.5)

    if len(candidate) == 1:
        return candidate
    
    # 候補のうちtargetより大きい値と小さい値を取り出す
    low = candidate[:1]
    high = candidate[1:]

    # 小さい値の方は他との組み合わせで近い値にならないか調査
    if low != [0]:
        low += dp_find(dp, target - low[0], resistor_values)

    # 誤差の少ない方を採用
    diff_high = abs(sum(high) - target)
    diff_low = abs(target - sum(low))
    if diff_high <= diff_low:
        return high
    else:
        return low


# limit個の組み合わせで最もtargetに近く、誤差が少ない値を探す
dp = [[0]]
dp = dp + [[]] * (target + 1)

for dp_idx in range(1, len(dp)):
    dp[dp_idx] = dp_find(dp, dp_idx, resistor_values)
print(list(map(lambda x:x/100, dp[target])))