人口1000万に近い都道府県名の組み合わせとその合計を表示させたい

Question

都道府県とその人口データの数字を組み合わせて1000万に近い組み合わせを求めたいです。
下記のコードは1000万に近い組み合わせの合計は出せたのですがその時計算に利用した都道府県名も表示させたいです。

空リストやappend関数を使うようですが勉強中につきよくわかりませんでした。

どなたかご教授していただけると助かります。お願いします。

goal = 10000000

jinkou = [
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
]

kenmei =[
'北海道','青森県','岩手県','宮城県','秋田県','山形県','福島県','茨城県','栃木県','群馬県',
'埼玉県','千葉県','東京都','神奈川県','新潟県','富山県','石川県','福井県','山梨県','長野県',
'岐阜県','静岡県','愛知県','三重県','滋賀県','京都府','大阪府','兵庫県','奈良県','和歌山県',
'鳥取県','島根県','岡山県','広島県','山口県','徳島県','香川県','愛媛県','高知県','福岡県',
'佐賀県','長崎県','熊本県','大分県','宮崎県','鹿児島県','沖縄県'
]

min_total = 0

def kumiawase(total,position):
global min_total
if position >= len(jinkou):
return
if total < goal:
if abs(goal - (total+jinkou[position])) < abs(goal - min_total):
min_total = total + jinkou[position]
kumiawase(total + jinkou[position],position + 1)
kumiawase(total,position + 1)

kumiawase(0,0)
print(min_total)

Answer 1

kumiawase関数に3番目の引数picksを追加して「(現在の組合せで)選択している県のposition番号リスト」を記録するようにしました。
また、合計が1,000万に一番近くなる組合せを記録するためbest_combinationを追加しました。

プログラムを実行すると [0, 1, 2, 20]番目の県/人口を選択すれば良いことが分かるので、
あとはkenmeiリストから県名を抜き出せば答えになります。

goal = 10000000

jinkou = [
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
]

kenmei =[
'北海道','青森県','岩手県','宮城県','秋田県','山形県','福島県','茨城県','栃木県','群馬県',
'埼玉県','千葉県','東京都','神奈川県','新潟県','富山県','石川県','福井県','山梨県','長野県',
'岐阜県','静岡県','愛知県','三重県','滋賀県','京都府','大阪府','兵庫県','奈良県','和歌山県',
'鳥取県','島根県','岡山県','広島県','山口県','徳島県','香川県','愛媛県','高知県','福岡県',
'佐賀県','長崎県','熊本県','大分県','宮崎県','鹿児島県','沖縄県'
]

min_total = 0
best_combination = []

def kumiawase(total, position, picks):
    global min_total
    if position >= len(jinkou):
        return
    if total < goal:
        if abs(goal - (total+jinkou[position])) < abs(goal - min_total):
            min_total = total + jinkou[position]
            best_combination[:] = picks + [position]
            kumiawase(total + jinkou[position],position + 1, picks + [position])
    kumiawase(total,position + 1, picks)

kumiawase(0, 0, [])
print(min_total)

print(best_combination)
print(' + '.join(f'{kenmei[b]}({jinkou[b]:,})' for b in best_combination))

# 10001495
# [0, 1, 2, 20]
# 北海道(5,381,733) + 青森県(1,308,265) + 岩手県(1,279,594) + 岐阜県(2,031,903)

Comments

[退会済みユーザー]

質問者さんのコードだとリストの先頭項目を優先的に扱っています。その結果選択するのは [0, 1, 2, 20] の 北海道, 青森県, 岩手県, 岐阜県 で 合計は 10,001,495人とのことでした。
合計を1,000万人にできるだけ近づけるという点では、この計算は正しくありません。
たとえば、[1, 3, 17, 20, 30, 35, 40, 41] (['青森県', '宮城県', '福井県', '岐阜県', '鳥取県', '徳島県', '佐賀県', '長崎県'])を選択すると、人口の合計はちょうど1,000万人になります。(他にも合計が1,000万人になる組み合わせは多数あります)

Answer 2

リスト prefs を用意して、それに県名を append していくのはどうでしょうか。
また、ソースコードのインデントが不明なので間違っていたらごめんなさいですが、 if total < goal: は if min_total < goal: ではないでしょうか。

min_total = 0
prefs = []
def kumiawase(total,position):
  global min_total, city
  if position >= len(jinkou):
    return
  if min_total < goal:
    if abs(goal - (total+jinkou[position])) < abs(goal - min_total):
      min_total = total + jinkou[position]
      prefs.append(kenmei[position])
      kumiawase(total + jinkou[position],position + 1)
    kumiawase(total,position + 1)

kumiawase(0,0)
print(min_total)
print(prefs)

#
10303491
['北海道', '青森県', '岩手県', '宮城県']