枝狩り

問題

都道府県からいくつかを選んで、その人口の合計が１千万人にもっと近い組み合わせとその人口を求めてください。

各都道府県の人口は、2015年（平成27年）の国勢調査に基づきます。

2015年(平成27年)国勢調査 各都道府県人口 - https://www.stat.go.jp/data/kokusei/2015/kekka.html

解き方・ソースコード

単純に全ての組み合わせを調べると、各都道府県を「選ぶ」「選ばない」の２通りがあり、４７都道府県で $ 2^{47} $ 通りを調べなければなりません。

これは現実的ではありません。

そこで枝狩りという手法を使います。

枝刈りとは、探索の途中において必要な条件を満たしているかどうかをチェックすることです。

必要な条件を満たしていなければ、そこで処理を中断します。

目的の1000万人を超えた場合、それ以上追加しても近づくことはありません。

また、それまでに調べた値より1000万人とのズレが大きいときも調べる必要はありません。

そこでこれらの条件を踏まえた上で、北海道から順に「選ぶ」「選ばない」のパターンを枝狩りしながら再帰的に探索します。

ズレを求めるには、1000万人との差の絶対値(abs関数)を使います。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 近づける値
goal = 10000000
# 各都道府県の人口（北海道から沖縄まで）
pref = [ 5381733, 1308265, 1279594, 2333899, 1023119, 1123891, 1914039, 2916976,
        1974255, 1973115, 7266534, 6222666, 13515271, 9126214, 2304264, 1066328,
        1154008, 786740, 834930, 2098804, 2031903, 3700305, 7483128, 1815865,
        1412916, 2610353, 8839469, 5534800, 1364316, 963579, 573441, 694352,
        1921525, 2843990, 1404729, 755733, 976263, 1385262, 728276, 5101556,
        832832, 1377187, 1786170, 1166338, 1104069, 1648177, 1433566 ]

min_total = 0
def search(total, pos):
    global min_total
    if pos >= len(pref):    # 人口データ探索終了
        return
    if total < goal:        # 枝狩り① 目標人口数を超えていない場合
        if abs(goal - (total + pref[pos])) < abs(goal - min_total): # 枝狩り② ズレが少ない場合
            min_total = total + pref[pos]                           # 合計値を更新
        search(total + pref[pos], pos + 1)      # 選ぶ場合（その都道府県の人口を足す）
        search(total, pos + 1)                  # 選ばない場合（その都道府県の人口を足さない）

search(0, 0)
print('解：', min_total)

[実行結果]

解： 10000000

青森県、宮城県、福井県、岐阜県、鳥取県、徳島県、佐賀県、長崎県の人口を合計するとちょうど10000000人になります。