Pythonで目標値に最も近い部分列の合計を見つけるプログラム

問題の概要

配列 nums と整数 goal が与えられます。ここから部分列(元の順序を保ちながら任意の要素を選んだもの)を1つ選び、その要素の合計 s が goal にできるだけ近づくようにします。言い換えれば、絶対差 |s − goal| を最小化することが目的です。

例として、nums = [8, -8, 16, -1]、goal = -3 が入力された場合を考えてみましょう。このとき出力は 2 になります。部分列 [8, -8, -1] を選ぶと合計は -1 となり、|-1 − (-3)| = 2 が達成可能な最小値だからです。

解法の考え方

すべての部分列を素朴に列挙すると、組み合わせの総数は O(2ⁿ) に膨れ上がり、現実的な時間内では処理できません。そこで本手法では、次のような工夫によって探索空間を大幅に削減しています。

• 絶対値の降順でソート: 影響の大きい要素から先に処理することで、早い段階で良好な暫定解(現在の最良値)が得られ、以降の枝刈りの精度が向上します。
• 残りの正負の累積和を前計算: 配列 pos(残りの正の数の合計)と neg(残りの負の数の合計)を事前に求めておくことで、「これ以上進んでも答えを改善できない状態」を即座に判定できます。
• 範囲チェックによる枝刈り: 集合 s 内の各部分和について、区間 [goal − ans, goal + ans] に到達し得るものだけを残し、それ以外は破棄します。
• 完全一致で即終了: 差が 0 になる組み合わせが見つかった時点でただちに 0 を返すため、無駄な探索が発生しません。

アルゴリズムの手順

1. n を nums のサイズとします。
2. nums を、要素の絶対値が大きい順に並べ替えます。
3. サイズ n+1 の配列 neg と pos を、それぞれ 0 で初期化します。
4. i を n−1 から 0 まで減らしながら処理します。nums[i] が負の場合は neg[i] = neg[i+1] + nums[i]、pos[i] = pos[i+1] とし、それ以外の場合は pos[i] = pos[i+1] + nums[i]、neg[i] = neg[i+1] とします。
5. ans を |goal| で初期化し、集合 s を {0} とします。
6. 関数 check(a, b) を「b < goal − ans または goal + ans < a のとき False、それ以外は True」を返すよう定義します。
7. i を 0 から n−1 まで動かし、check(x + neg[i], x + pos[i]) が真となる s 内の要素 x だけで集合を作り直します。候補が空になった時点でループを打ち切ります。
8. 残った各 x に対して y = x + nums[i] を計算し、|y − goal| が ans より小さければ ans を更新します。ans が 0 になれば即座に 0 を返します。
9. 最終的な ans を返します。

Pythonでの実装例

理解を深めるために、実際の実装を見てみましょう。

from collections import Counter

def solve(nums, goal):
    n = len(nums)
    nums.sort(key=lambda x: -abs(x))
    neg = [0 for _ in range(n+1)]
    pos = [0 for _ in range(n+1)]
    for i in range(n-1, -1, -1):
        if nums[i] < 0:
            neg[i] = neg[i+1] + nums[i]
            pos[i] = pos[i+1]
        else:
            pos[i] = pos[i+1] + nums[i]
            neg[i] = neg[i+1]
    ans = abs(goal)
    s = set([0])

    def check(a, b):
        if b < goal - ans or goal + ans < a:
            return False
        return True

    for i in range(n):
        sl = [x for x in s if check(x+neg[i], x+pos[i])]
        if len(sl) == 0:
            break
        s = set(sl)
        for x in sl:
            y = x + nums[i]
            if abs(y - goal) < ans:
                ans = abs(y - goal)
            if ans == 0:
                return 0
            s.add(y)
    return ans

nums = [8,-8,16,-1]
goal = -3
print(solve(nums, goal))

入力

[8,-8,16,-1], -3

出力

2

この例では、部分列 [8, -8, -1] の合計 -1 が目標値 -3 に最も近く、絶対差は 2 となります。これより小さい差を実現する部分列は存在しないため、2 が正解です。

まとめ

このアルゴリズムは、単純な全探索では指数時間かかる問題に対して、ソートによる処理順序の工夫と累積和を利用した枝刈りを組み合わせることで、実用的な速度で最適解を求められる点がポイントです。部分和問題やナップサック問題など、類似の「合計をターゲットに近づける」系の問題にも応用できるテクニックなので、ぜひ覚えておきましょう。