そういえばふるさと納税、まだやってなかったなぁということで、駆け込みでふるさと納税の申請を行っていた。

ふるさと納税とは寄附金のうち2,000円を超える部分で所得税の還付 、住民税の控除が受けられる、という制度。

寄附を行うと自治体によってさまざまな返礼品がもらえる。

控除が受けられる寄附金の上限額は収入や家族構成によって異なる。

言い換えると実質2,000円で返礼品を入手することのできる制度。

もちろん社会的な意義もあるのだろうが、この解釈であらかた認識は間違っていないと思う。

また、寄附については複数のものを組み合わせられるのが特徴だ。

ナップサック問題と同じ

よくよく考えるとふるさと納税の申請行為はナップサック問題と似ているということに気づく。

ナップサック問題ではナップサックに詰められる重さの上限と各アイテムの重さと価値が与えられる。

重さが超えないように価値を最大化したい場合の価値はいくつか？ということを求める問題だ。

ふるさと納税の場合では、寄附金の上限に対して、寄附金の額と返礼品の価値を考える。

そうすれば、同じ手続きで（あくまで金額的な）価値を最大化する組み合わせを発見することができる。

最大化できる価値の算出

前準備としてふるさと納税還元率ランキングベスト300というサイトを参考に以下のようなデータを作ってみた。

ふるさと納税還元率ランキングベスト300

二次元リストで、返礼品の名前、寄附金の額、返礼品の金額を記録している。

返礼品の金額については還元率を元に適当に数字をまるめて計算した。

例えば一番最初の訳あり牛タンはサイトの調査によると、寄附金が19,000円で還元率が140.0%らしい。

つまり返礼品の価値は19,000 x 1.4で26,600円となる。

data = [['＼発送時期が選べる/ ＼訳あり/ 牛タン', 19000, 26600],
        ['どっちのハンバーグ!?デミグラスソース2', 9000, 9801],
        ['[お届け月が選べる]国産牛 赤身切り落と', 10000, 10760],
        ['ふるさと納税 おかず 四万十ひすい餃子・', 15000, 15480],
        ['[発送時期が選べる]鹿児島県産黒毛和牛ス', 25000, 25000],
        ['自分のこだわりの焼き加減で調理可能! 佐', 10000, 10000],
        ['博多の味本舗 辛子明太子切れ子1kg(6', 10000, 9820],
        ['[さとふる限定]博多の味本舗 辛子明太子', 10000, 9820],
        ['おおいた味力 ソーセージ セット 6種 ', 10000, 9600],
        ...
        ]

print(len(data))
>>>
300

300アイテムすべて登録してみた。

まずはナップサック問題に沿って、最大化された価値を確認してみる。

# 行数が多いので別ファイルに
from data import data

# データの個数
N = len(data)
# 寄附金の上限　仮に55,000円とした
LIMIT = 55000

# 返礼品の名称リスト
items = ['']
# 寄附金のリスト
amounts = [0]
# 返礼品の価値リスト
values = [0]

# dataを繰り返してそれぞれに加える
for i in range(N):
    item, amount, val = data[i]
    items.append(item)
    amounts.append(amount)
    values.append(val)

# dpテーブルの作成
# 横軸が金額、縦軸がアイテム
dp = [[0] * (LIMIT + 1) for i in range(N + 1)]

# 商品の数だけ繰り返す
for i in range(N + 1):
    amo = amounts[i]
    val = values[i]
    # 金額の数だけ繰り返す
    for j in range(LIMIT + 1):
        # 商品を加えない場合の価値
        ref = dp[i - 1][j]
        if j - amo < 0:
            dp[i][j] = ref
        else:
            # 商品を加えた場合
            add_case = dp[i - 1][j - amo] + val
            # 大きい方を記録する
            dp[i][j] = max(ref, add_case)

print(dp[N][LIMIT])
>>>
64021

上限55,000円とした場合は64,021円分が最大化された価値であることが分かる。

どの商品が選ばれたか

現状では、64,021円が最大価値らしいことが分かったが、どの商品が選ばれたのかが分からない。

dpテーブルとは別に選んだ商品を記録するテーブルを作るとこの問題を解決できる。

from data import data

N = len(data)
LIMIT = 55000

items = ['']
amounts = [0]
values = [0]

for i in range(N):
    item, amount, val = data[i]
    items.append(item)
    amounts.append(amount)
    values.append(val)

dp = [[0] * (LIMIT + 1) for i in range(N + 1)]
# 0 or 1でどの商品を選んだかを管理する
choice = [[""] * (LIMIT + 1) for _ in range(N + 1)]

for i in range(N + 1):
    amo = amounts[i]
    val = values[i]
    for j in range(LIMIT + 1):
        ref = dp[i - 1][j]
        if j - amo < 0:
            dp[i][j] = ref
            # 現在みている商品は選べないので0
            choice[i][j] = choice[i - 1][j] + '0'
        else:
            add_case = dp[i - 1][j - amo] + val
            dp[i][j] = max(ref, add_case)
            # 今見ている商品を加えた方がいい場合
            if add_case > ref:
                # 1を加える
                choice[i][j] = choice[i - 1][j - amo] + '1'
            else:
                choice[i][j] = choice[i - 1][j] + '0'

print(dp[N][LIMIT])
print(choice[N][LIMIT])
>>>
64021
01111000000000....

後はchoiceを繰り返して答えを出力すればどの商品を頼むべきかが分かる。

print(f'上限:{LIMIT}円の場合')
print('----注文リスト----')
a_sum_amount = 0
for i, bit in enumerate(choice[N][LIMIT]):
    if bit == '1':
        print(f'商品名:{items[i]}, 寄附金額:{amounts[i]}, 返礼品価値:{values[i]}')
        a_sum_amount += amounts[i]
print('----------------')
value_max = dp[N][LIMIT]

print(f'合計寄附金額:{a_sum_amount},合計返礼品価値:{value_max}')
>>>
上限:55000円の場合
----注文リスト----
商品名:＼発送時期が選べる/ ＼訳あり/ 牛タン, 寄附金額:19000, 返礼品価値:26600
商品名:どっちのハンバーグ!?デミグラスソース2, 寄附金額:9000, 返礼品価値:9801
商品名:[お届け月が選べる]国産牛 赤身切り落と, 寄附金額:10000, 返礼品価値:10760
商品名:ふるさと納税 おかず 四万十ひすい餃子・, 寄附金額:15000, 返礼品価値:15480
商品名:黒豆珈琲 レギュラーコーヒー, 寄附金額:2000, 返礼品価値:1380
----------------
合計寄附金額:55000,合計返礼品価値:64021

他の場合でも試してみよう。

例えば75,000円の場合。

上限:75000円の場合
----注文リスト----
商品名:＼発送時期が選べる/ ＼訳あり/ 牛タン, 寄附金額:19000, 返礼品価値:26600
商品名:どっちのハンバーグ!?デミグラスソース2, 寄附金額:9000, 返礼品価値:9801
商品名:[お届け月が選べる]国産牛 赤身切り落と, 寄附金額:10000, 返礼品価値:10760
商品名:ふるさと納税 おかず 四万十ひすい餃子・, 寄附金額:15000, 返礼品価値:15480
商品名:自分のこだわりの焼き加減で調理可能! 佐, 寄附金額:10000, 返礼品価値:10000
商品名:博多の味本舗 辛子明太子切れ子1kg(6, 寄附金額:10000, 返礼品価値:9820
商品名:黒豆珈琲 レギュラーコーヒー, 寄附金額:2000, 返礼品価値:1380
----------------
合計寄附金額:75000,合計返礼品価値:83841

105,000円の場合。

上限:105000円の場合
----注文リスト----
商品名:＼発送時期が選べる/ ＼訳あり/ 牛タン, 寄附金額:19000, 返礼品価値:26600
商品名:どっちのハンバーグ!?デミグラスソース2, 寄附金額:9000, 返礼品価値:9801
商品名:[お届け月が選べる]国産牛 赤身切り落と, 寄附金額:10000, 返礼品価値:10760
商品名:ふるさと納税 おかず 四万十ひすい餃子・, 寄附金額:15000, 返礼品価値:15480
商品名:[発送時期が選べる]鹿児島県産黒毛和牛ス, 寄附金額:25000, 返礼品価値:25000
商品名:自分のこだわりの焼き加減で調理可能! 佐, 寄附金額:10000, 返礼品価値:10000
商品名:博多の味本舗 辛子明太子切れ子1kg(6, 寄附金額:10000, 返礼品価値:9820
商品名:浅野農場どでかシューマイセット, 寄附金額:6000, 返礼品価値:5472
商品名:料理の友 にんにく胡麻醤油 郵送 100, 寄附金額:1000, 返礼品価値:870
----------------
合計寄附金額:105000,合計返礼品価値:113803

おわりに

ナップサック問題を解くのと同じ方法でふるさと納税の返礼品の価値を最大化できることが分かった。

今回はサイトで紹介されたものを適当にピックしたので食品だらけの結果となった。

このあたりは適宜ほしいものと金額をメモっておけば良い感じに自分がほしい且つ金額的も最適化されてる組み合わせが得られると思う。

けど適宜やる、ってのがいちばん難しいんだよな。ではでは。