準備
- Google Colaboratory（※Jupyter NotebookでもOK）
- 配布ソースコード（※一からやりたい方は不要）
使用技術
Python
Qiskit
やったこと
ふるさと納税上限シミュレーション × 楽天API連携 × 量子コンピューティング × 最適化問題
「ふるさと納税 訳あり」で
楽天APIからふるさと納税返礼品一覧を取得して
組合せ最適化問題のひとつナップサック問題を解く量子アルゴリズム
（QAOA:量子近似最適化アルゴリズム）で
シミュレーションで出した控除上限額までで
最も総重量が重くなるような返礼品の組み合わせを求めて
とにかくふるさと納税で得するためのプログラムを組みました。
コメント
あと出てきますが、
楽天APIの検索ワードに「訳あり」と含めるのはケチ感を増幅させるためです。
数学やアルゴリズム、最新技術、データを使って
いかにして誰かの問題を解決するかという
ユーザー、ビジネス、技術を重視しています。
量子アルゴリズムでのやり方は現状使い物にはなりませんが、
古典的な（便宜上そう言うしかない）プログラムは使い物になりそうです。
しかし、控除上限額詳細シミュレーションはそこそこの精度しかないです。
“ちゃんとやる”ならGoogle先生のみでなく強い税理士が必要です。
（知り合いの税理士が所長を巻き込まないといけないくらい）
正確な計算や早い処理を求めるなら
量子コンピューティングとふるさと納税の根本レベルの原理にとことんまで精通するか
パッケージと簡単シミュレーションに妥協するかどちらかです。
QAOA（量子近似最適化アルゴリズム）について
量子断熱計算(QAA)における終状態(最適解を導くハミルトニアン)を$C$、また初期状態(基底エネルギー状態のハミルトニアン)を$B$とする。
ここで、任意の角度パラメータとして、ガンマ$(γ)$及びベータ$(β)$を用いて、$C$と$γ$に関するユニタリ行列を$U(C,γ)$、$B$と$β$に関するユニタリ行列を$U(B,β)$と定義。
$$
U(C, γ) = e^{iγC}…①\
U(C, β) = e^{iγB}…②
$$
さらに、上記のユニタリ行列を用いた反復計算回数を整数$p$とし、$(γ1,γ2,…,γp)$を要素とするベクトルを$γ、(β1,β2,…,βp)$を要素とするベクトルを$β$、p次元の直交基底ベクトルを$|s〉$として、以下の演算子$|γ,β〉$を定義。
$$
|γ, β> = U(B, βp)U(C, γ_p)U(B, β{p-1})U(C, γ_{p-1})…U(B, β_1)U(C, γ_1)|s>…③
$$
次に、上記で定義した演算子$|γ,β〉$を用いて、最適解を導くハミルトニアン$C$の期待値$Fp$を以下のように求める。
$$
F_p(γ, β) = <γ,β|C|γ,β>…④
$$
角度パラメータ$γ$及び、$β$を変化させ、$F_pが取りうる最大値M_pを探索。$
$$
M_p = max_{γ,β}F_p(γ,β)…⑤
$$
最大値M_pが求められた時、その時のγ,βが決定し、④について$C$の期待値が求まると同時に、最適解を与える組み合わせの状態が求まる。
- ユニタリ行列: 複素正方行列
- ハミルトニアン: 系の全エネルギー
- 系: なにかしらのまとまり
- 期待値: 予測される平均値
- イジングモデル: ２つの状態をとる格子点で構成された、格子模型
ナップサック問題について
定義
$I={1,2,…,N}$を品物の集合.
各品物$i \in I$の重みを$w_i$
価値を$v_i$
品物の重量の合計の上限を$W$とするとき
次のようにあらわされるものをナップサック問題という。
$$
max ∑{i \in I}v_iw_i\ s.t. ∑{i \in I}v_iw_i\le W\
x\in \mathbb{N}(\forall \in I)
$$
ここで、$x_i$はナップサックへ入れる品物の個数を表している。
解法
この問題は、もしも全数探索を行えば「品物を選ぶ・選ばない」の2通りの選択肢を品物の個数分だけ試すことになり、その計算量は$O(2^{|I|})$になる。しかし、効率の良い貪欲法による解法が知られており，ここではその解法を示す。この問題における漸化式は
$$
V(i,w)
=\begin{cases}
{0\quad if\;i= 0\,or\,w = 0}\
{V(i-1,w)\quad if\;w_i>w}\
{max(V(i-1),V(i-1,w-w_i)+v_i)\quad otherwise}
\end{cases}
$$
となる。ここで $V(i, w)$ の値は重量の合計が$w$以下である場合に，添字が$i$以下の品物を使って実現できる価値の合計の最大値を表す。この式は
- 「1つも品物を選べない」あるいは「最大重量が ${\displaystyle 0}{\displaystyle 0}$」であるときには、詰め込める品物がないので選ばれた品物の価値の合計を ${\displaystyle 0}{\displaystyle 0}$ とする
- 品物 ${\displaystyle i}$ の重さが ${\displaystyle w}$ を超えている場合は、品物 ${\displaystyle i}$ は追加できないから、価値の合計は品物の添字の上限が1つ前までのものの価値の最大値になる
- 品物 ${\displaystyle i}$ の重さが ${\displaystyle w}$ を越えていない場合には、品物 ${\displaystyle i}$ を追加しない場合と追加をする場合の価値の最大値の両方のうちで、小さくない方の値にする。
ということを表している。擬似コードは次の通り。価値の合計の最大値は $V(|I|, W)$ として得られる。さらに選んだ品物の列挙をするにはコードの追加が要る。
- 漸化式: 数列のある項をその前の項でで表したやつ
量子アニーリングのイジングモデルでナップサックを解くための定式
$イジングモデルで解く際ののハミルトニアンの定義
$H = B\Bigl(W-\sum_iw_ix_i\Bigl)^2-\sum_iv_ix_i$
*$B$ = ハイパーパラメータ
プログラム
パッケージインストール
!pip install matplotlib
!pip install seaborn
!pip install japanize-matplotlib
!pip install qiskit_optimization
!pip install qiskit-aer
!pip install ortoolpy
!pip install pulpパッケージインポート
from typing import List
import math
from qiskit_optimization.applications import Knapsack
from qiskit.algorithms import QAOA, NumPyEigensolver, NumPyMinimumEigensolver
from qiskit.utils import QuantumInstance
from qiskit import Aer
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from typing import List
from ortoolpy import knapsack
from pulp import *
import requests
import numpy as np
import pandas as pd
import time
import japanize_matplotlib
import copy
import random
from IPython.display import HTML
%matplotlib inlineふるさと納税控除限度額計算クラスを定義
class Calculator():
income: int = 0 # 総所得
donation_amount: int = 0 # 寄附金額
resident_tax: int = 0 # 住民税額
def __init__(self, income: int, donation_amount: int, resident_tax: int):
self.income = income
self.donation_amount = donation_amount
self.resident_tax = resident_tax
# 控除上限額を考慮したふるさと納税の控除額の結果
def deduction_result(self):
# 所得税からの控除限度額＝総所得の40％以下、住民税基本分からの控除限度額＝総所得の30％以下、住民税特例分からの控除限度額＝個人住民税所得割額の20%のいずれかに街道
if (self.income_tax_deduction() <= self.income * 0.4) or (self.basic_resident_tax_deduction() <= self.income * 0.3) or (self.special_inhabitant_tax_deduction() <= self.income * 0.2):
return self.deduction_limit()
else:
return self.hometown_tax_deduction()
# 控除限度額
def deduction_limit(self):
# 個人住民税所得割額×20% / 100％－住民税基本分10％－（所得税率×復興税率1.021）+ 負担金2,000円
return (self.resident_tax * 0.2 / (1 - 0.1) - (self.income_tax_rate() * 1.021)) + 2000
# ふるさと納税の控除額
def hometown_tax_deduction(self):
# 所得税分の控除額＋住民税基本分の控除額＋住民税特例分の控除額
return self.income_tax_deduction() + self.basic_resident_tax_deduction() + self.special_inhabitant_tax_deduction()
# 所得税分の控除額
def income_tax_deduction(self):
# （ふるさと納税の寄付金額 － 2,000円）×（所得税の税率（0～45%)×1.021）
return (self.donation_amount - 2000) * (self.income_tax_rate() * 1.021)
# 住民税基本分の控除額
def basic_resident_tax_deduction(self):
# （ふるさと納税の寄付金額 － 2,000円）×10％
return (self.donation_amount - 2000) * 0.1
# 住民税特例分の控除額
def special_inhabitant_tax_deduction(self):
# （ふるさと納税の寄付金額 － 2,000円）×（90％ － 所得税率×1.021）※1
return (self.donation_amount - 2000) * (0.9 - (self.income_tax_rate() * 1.021))
# 所得税率
def income_tax_rate(self):
tax_rate = [0.05, 0.10, 0.20, 0.23 ,0.33 , 0.40, 0.45]
borders = [i*10000 for i in [0, 195, 330, 695, 900, 1800, 4000, np.inf]]
deduction = [0, 97500, 427500, 636000, 1536000, 2796000, 4976000]
special_tax = 0.021
step = len(tax_rate)
answer = 0
i = 0
while i <= step:
if (self.income >= borders[i]) and (self.income < borders[i+1]):
answer = tax_rate[i]
i+=1
return answerふるさと納税控除上限詳細シミュレーションクラスを定義
class Simulator():
my_income: int = 0 # あなたの給与収入
spouse_income: int = 0 # 配偶者の給与収入(夫または妻)
listed_capital_gain: int = 0 # 株式譲渡益(上場)
unlisted_capital_gain: int = 0 # 株式譲渡益(非上場)
total_income: int = 0 # 所得の合計
spouse: int = 0 # 配偶者
spouses: List[str] = ['なし', 'あり(69歳以下)', 'あり(70歳以上))'] # 配偶者の有無
widow: int = 0 # 寡婦
widows: List[str] = ['非該当', '寡婦', 'ひとり親(女性)', 'ひとり親(男性)'] # 寡婦に該当しますか
has_handicap: int = 0 # 障害者の有無
handicap = { # 障害者
"general": 0, # 一般(人)
"separated_special": 0, # 別居特別(人)
"together_special": 0 # 同居特別(人)
}
has_support: int = 0 # 扶養家族の有無
support = { # 扶養家族の人数(夫または妻以外)
"under_15": 0,
"from_16_to_18": 0,
"from_19_to_22": 0,
"from_23_to_69": 0,
"over_70": 0,
}
spouse_deduction: int = 0 # 配偶者控除額
widow_deduction: int = 0 # 寡婦控除
handicap_deduction: int = 0 # 障害者控除
support_deduction: int = 0 # 扶養控除
basic_deduction: int = 0 # 基礎控除
social_insurance_premium: int = 0 # 社会保険料等の金額
small_scale_enterprise_matual_aid_premium :int = 0 # 小規模企業共済等掛金の金額
life_insurance_premium_deduction: int = 0 # 生命保険料の控除額
earthquake_insurance_premium_deduction: int = 0 # 地震保険料の控除額
medical_expense_deduction: int = 0 # 医療費控除の金額
housing_loans_special_deduction: int = 0 # 住宅借入金等特別控除額
income_deduction: int = 0 # 給与所得控除額
total_deductin: int = 0 # 控除の合計
taxable_income: int = 0 # 課税所得金額
resident_tax: int = 0 # 住民税額
donation_amount: int = 0 # 寄附金額
def start(self):
print('★ふるさと納税寄附上限診断★')
print()
print('※入力する値において、ない場合は0を入力')
print()
print('給与')
self.income_section()
print()
print('家族構成')
self.famiry_section()
print()
print('保険、控除等')
self.insurance_and_deduction_section()
print()
self.total_deductin = self.social_insurance_premium + self.small_scale_enterprise_matual_aid_premium + self.life_insurance_premium_deduction + self.earthquake_insurance_premium_deduction + self.earthquake_insurance_premium_deduction + self.medical_expense_deduction + self.housing_loans_special_deduction + self.income_deduction + self.spouse_deduction + self.widow_deduction + self.handicap_deduction + self.support_deduction + self.basic_deduction
self.taxable_income = self.total_income - self.total_deductin
if self.taxable_income < 0:
self.taxable_income = 0
self.resident_tax = self.taxable_income * 0.1 # 税理士いわく、住民税は"ざっくり"収入から控除等の金額を引いたものの10%
self.donation_amount = int(input('寄附金額'))
print()
calculator = Calculator(self.my_income, self.donation_amount, self.resident_tax)
result = math.floor(calculator.deduction_limit())
return result
def income_section(self):
self.my_income = int(input('あなたの給与収入(円)'))
self.spouse_income = int(input('配偶者の給与収入(夫または妻)(円)'))
self.listed_capital_gain = int(input('株式譲渡益(上場)(円)'))
self.unlisted_capital_gain = int(input('株式譲渡益(非上場)(円)'))
self.total_income = self.my_income + self.spouse_income + self.listed_capital_gain + self.unlisted_capital_gain
def famiry_section(self):
self.__select_spouse()
self.__select_widow()
self.__select_handicap()
self.__select_support()
# 本人の合計所得
total_income = self.my_income + self.listed_capital_gain + self.unlisted_capital_gain
if self.spouse_income <= 480000:
# 配偶者控除
if self.spouse == 2:
if total_income <= 9000000:
self.spouse_deduction = 380000
elif (total_income > 9000000) and (total_income <= 9500000):
self.spouse_deduction = 260000
elif (total_income > 9500000) and (total_income <= 10000000):
self.spouse_deduction = 130000
else:
self.spouse_deduction = 0
elif self.spouse == 3:
if total_income <= 9000000:
self.spouse_deduction = 480000
elif (total_income > 9000000) and (total_income <= 9500000):
self.spouse_deduction = 320000
elif (total_income > 9500000) and (total_income <= 10000000):
self.spouse_deduction = 160000
else:
self.spouse_deduction = 0
else:
self.spouse_deduction = 0;
else:
# 配偶者特別控除
if total_income <= 9000000:
if (self.spouse_income > 480000) and (self.spouse_income <= 950000):
self.spouse_deduction = 380000
elif (self.spouse_income > 950000) and (self.spouse_income <= 1000000):
self.spouse_deduction = 360000
elif (self.spouse_income > 1000000) and (self.spouse_income <= 1050000):
self.spouse_deduction = 310000
elif (self.spouse_income > 1050000) and (self.spouse_income <= 1100000):
self.spouse_deduction = 260000
elif (self.spouse_income > 1100000) and (self.spouse_income <= 1150000):
self.spouse_deduction = 210000
elif (self.spouse_income > 1150000) and (self.spouse_income <= 1200000):
self.spouse_deduction = 160000
elif (self.spouse_income > 1200000) and (self.spouse_income <= 1250000):
self.spouse_deduction = 110000
elif (self.spouse_income > 1250000) and (self.spouse_income <= 1300000):
self.spouse_deduction = 60000
elif (self.spouse_income > 1300000) and (self.spouse_income <= 1330000):
self.spouse_deduction = 30000
else:
self.spouse_deduction = 0
elif (total_income > 9000000) and (total_income <= 9500000):
if (self.spouse_income > 480000) and (self.spouse_income <= 950000):
self.spouse_deduction = 260000
elif (self.spouse_income > 950000) and (self.spouse_income <= 1000000):
self.spouse_deduction = 240000
elif (self.spouse_income > 1000000) and (self.spouse_income <= 1050000):
self.spouse_deduction = 210000
elif (self.spouse_income > 1050000) and (self.spouse_income <= 1100000):
self.spouse_deduction = 180000
elif (self.spouse_income > 1100000) and (self.spouse_income <= 1150000):
self.spouse_deduction = 140000
elif (self.spouse_income > 1150000) and (self.spouse_income <= 1200000):
self.spouse_deduction = 110000
elif (self.spouse_income > 1200000) and (self.spouse_income <= 1250000):
self.spouse_deduction = 80000
elif (self.spouse_income > 1250000) and (self.spouse_income <= 1300000):
self.spouse_deduction = 40000
elif (self.spouse_income > 1300000) and (self.spouse_income <= 1330000):
self.spouse_deduction = 20000
else:
self.spouse_deduction = 0
elif (total_income > 9500000) and (total_income <= 10000000):
if (self.spouse_income > 480000) and (self.spouse_income <= 950000):
self.spouse_deduction = 130000
elif (self.spouse_income > 950000) and (self.spouse_income <= 1000000):
self.spouse_deduction = 120000
elif (self.spouse_income > 1000000) and (self.spouse_income <= 1050000):
self.spouse_deduction = 110000
elif (self.spouse_income > 1050000) and (self.spouse_income <= 1100000):
self.spouse_deduction = 90000
elif (self.spouse_income > 1100000) and (self.spouse_income <= 1150000):
self.spouse_deduction = 70000
elif (self.spouse_income > 1150000) and (self.spouse_income <= 1200000):
self.spouse_deduction = 60000
elif (self.spouse_income > 1200000) and (self.spouse_income <= 1250000):
self.spouse_deduction = 40000
elif (self.spouse_income > 1250000) and (self.spouse_income <= 1300000):
self.spouse_deduction = 20000
elif (self.spouse_income > 1300000) and (self.spouse_income <= 1330000):
self.spouse_deduction = 10000
else:
self.spouse_deduction = 0
else:
self.spouse_deduction = 0
if total_income <= 5000000:
# 寡婦控除
if self.widow == 1:
self.widow_deduction = 270000
# ひとり親控除
elif (self.widow == 2) or (self.widow == 3):
self.widow_deduction = 350000
else:
self.widow_deduction = 0
else:
self.widow_deduction = 0
# 障がい者控除
if self.has_handicap == 1:
self.handicap_deduction = 270000 * self.handicap['general'] + 400000 * self.handicap['separated_special'] + 750000 * self.handicap['together_special']
else:
self.handicap_deduction = 0
# 扶養控除
if self.has_support == 1:
self.support_deduction = 380000 * self.support['from_16_to_18'] + 630000 * self.support['from_19_to_22'] + 480000 * self.support['from_23_to_69'] + 580000 * self.support['over_70']
else:
self.support_deduction = 0
def insurance_and_deduction_section(self):
self.social_insurance_premium = int(input('社会保険料等の金額(円)'))
self.small_scale_enterprise_matual_aid_premium = int(input('小規模企業共済等掛金の金額(円)'))
self.life_insurance_premium_deduction = int(input('生命保険料の控除額(円)'))
self.earthquake_insurance_premium_deduction = int(input('地震保険料の控除額(円)'))
self.medical_expense_deduction = int(input('医療費控除の金額(円)'))
self.housing_loans_special_deduction = int(input('住宅借入等特別控除額(円)'))
# 所得控除
if self.total_income < 1625000:
self.income_deduction = 550000
elif (self.total_income >= 1625001) and (self.total_income < 1800000):
self.income_deduction = self.total_income * 0.4 - 100000
elif (self.total_income >= 1800001) and (self.total_income < 3600000):
self.income_deduction = self.total_income * 0.3 + 80000
elif (self.total_income >= 3600001) and (self.total_income < 6600000):
self.income_deduction = self.total_income * 0.2 + 440000
elif (self.total_income >= 6600001) and (self.total_income < 8500000):
self.income_deduction = self.total_income * 0.1 + 1100000
else:
self.income_deduction = 1950000
# 基礎控除
if self.total_income <= 24000000:
self.basic_deduction = 480000
elif (self.total_income > 24000000) and (self.total_income <= 24500000):
self.basic_deduction = 320000
elif (self.total_income > 24000000) and (self.total_income <= 25000000):
self.basic_deduction = 160000
else:
self.basic_deduction = 0
def __select_spouse(self):
print('配偶者の有無')
for i, sponse in enumerate(self.spouses):
print(str(i+1) + '. ' + sponse)
self.spouse = int(input('番号を選んでください。'))
def __select_widow(self):
print('寡婦に該当しますか？')
for i, widow in enumerate(self.widows):
print(str(i+1) + '. ' + widow)
self.widow = int(input('番号を選んでください。'))
def __select_handicap(self):
self.has_handicap = int(input('障害者の有無 1. あり, 2. なし'))
if self.has_handicap == 1:
self.handicap['general'] = int(input('一般の障害者(人)'))
self.handicap['separated_special'] = int(input('本人・別居の特別障害者(人)'))
self.handicap['together_special'] = int(input('同居の特別障害者(人)'))
def __select_support(self):
self.has_support = int(input('扶養家族の有無 1. あり, 2. なし'))
if self.has_support == 1:
self.support['under_15'] = int(input('15歳以下'))
self.support['from_16_to_18'] = int(input('16歳-18歳'))
self.support['from_19_to_22'] = int(input('19歳-22歳'))
self.support['from_23_to_69'] = int(input('23歳-69歳'))
self.support['over_70'] = int(input('70歳以上'))様々な方法でナップサック問題を解く方法を定義
class KnapsackProblem():
values: List[int] = []
weights: List[int] = []
max_weight: int = 0
def __init__(self, values, weights, max_weight):
self.values = values
self.weights = weights
self.max_weight = max_weight
def solve_by_qaoa(self):
problem = Knapsack(values=self.values, weights=self.weights, max_weight=self.max_weight)
quadratic_program = problem.to_quadratic_program()
backend = Aer.get_backend('aer_simulator')
quantum_instance = QuantumInstance(backend=backend, shots=800, seed_simulator=99)
min_eigen_optimizer = MinimumEigenOptimizer(min_eigen_solver=QAOA(reps=1, quantum_instance=quantum_instance))
solved = min_eigen_optimizer.solve(quadratic_program)
result = problem.interpret(solved)
print(result)
return result
def solve_by_numpy_eigensolver(self):
problem = Knapsack(values=self.values, weights=self.weights, max_weight=self.max_weight)
quadratic_program = problem.to_quadratic_program()
min_eigen_optimizer = MinimumEigenOptimizer(min_eigen_solver=NumPyMinimumEigensolver())
solved = min_eigen_optimizer.solve(quadratic_program)
result = problem.interpret(solved)
print(result)
return result
def solve_by_ortoolpy(self):
result = knapsack(self.weights, self.values, self.max_weight)
print(result)
return result
def solve_by_pulp(self):
ran = range(len(self.values))
problem = LpProblem(sense=LpMaximize)
var = [LpVariable('x%d'%i, cat=LpBinary) for i in ran]
problem += lpDot(self.weights, var)
problem += lpDot(self.values, var) <= self.max_weight
problem.solve()
result = (value(problem.objective), [i for i in ran if value(var[i]) > 0.5])
print(result)
return result
def solve_by_greedy_algorithm(self):
N = len(self.values)
W = self.max_weight
w = self.weights
v = self.values
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
for j in range(W+1):
if j < w[i]:
dp[i+1][j] = dp[i][j]
else:
dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
result = dp[N][W]
print(result)
return result
def solve_by_ising_model(self):
def Hamiltonian(x):
B = 10
W = self.max_weight
w_sum = 0
v_sum = 0
for i, w in enumerate(self.weights):
w_sum += w*x[i]
for i, v in enumerate(self.values):
v_sum += v*x[i]
H = B*(W-w_sum)**2-v_sum
return H
def run(H):
N = len(self.values)
T = self.max_weight
ite = 1000
targetT = 0.02
red = 0.97
q = [random.randint(0,1) for i in range(N)]
# q = [1,1,1,1,0,0,0,0,0,0]
while T>targetT:
x_list = np.random.randint(0, N, ite)
for x in x_list:
q2 = copy.copy(q)
y = np.random.randint(0, N)
q2[x] = q[y]
q2[y] = q[x]
dE = H(q2) - H(q)
if np.exp(-dE/T) > np.random.random_sample():
q[x] = q2[x]
q[y] = q2[y]
T *= red
return q
answer = run(Hamiltonian)
result = []
for i, a in enumerate(answer):
if a == 1:
result.append(i)
print(result)
return楽天APIから商品一覧を取得する
REQUEST_URL = "https://app.rakuten.co.jp/services/api/IchibaItem/Search/20170706"
APP_ID="<楽天APIのアプリID>"
serch_keyword = 'ふるさと納税 訳あり'
serch_params = {
"format" : "json",
"keyword" : serch_keyword,
"applicationId" : [APP_ID],
"availability" : 0,
"hits" : 30,
"sort" : "standard",
"postageFlag" : 1
}
item_list = []
max_page = 10
for page in range(1, max_page+1):
response = requests.get(REQUEST_URL, serch_params)
result = response.json()
item_key = ['itemName', 'itemPrice', 'itemCaption', 'shopName', 'shopUrl', 'itemUrl']
for i in range(0, len(result['Items'])):
time.sleep(1)
tmp_item = {}
item = result['Items'][i]['Item']
for key, value in item.items():
if key in item_key:
tmp_item[key] = value
item_list.append(tmp_item.copy())
df = pd.DataFrame(item_list)
df.drop_duplicates(subset=['itemUrl'], inplace=True) # 重複削除
df = df.reindex(columns=['itemName', 'itemPrice', 'itemCaption', 'itemUrl', 'shopName', 'shopUrl'])
df.columns = ['商品名', '商品価格', '商品説明文', '商品URL', '店舗名', '店舗URL']
df.index = df.index + 1
# 量がわかる商品のみ抽出
weight = df['商品名'].str.contains('kg')
df = df[weight]
df['kg'] = df['商品名'].str.extract('([0-9]+)kg')
df = df.reindex(columns=['商品名', 'kg', '商品価格', '商品説明文', '商品URL', '店舗名', '店舗URL']データ確認
df.head()
df.plot(title='重さと値段の関係性')
実用的な解法（ortoolpyに頼る）
def practical_solution():
simulator = Simulator()
weights = [int(data) for i, data in enumerate(df['kg'])]
prices = [int(data) for i, data in enumerate(df['商品価格'])]
deduction_limit = simulator.start()
# ナップサックの場合、ものの値段等が価値で、重さによる制限がある。今回の場合、ものの重さを価値として、値段の制限がある。
knapsack_problem = KnapsackProblem(values=weights, weights=prices, max_weight=deduction_limit)
result = knapsack_problem.solve_by_ortoolpy()
print(f'控除上限額は{deduction_limit}円')
HTML(df.to_html(render_links=True, escape=False))
def make_clickable(val):
return f'<a target="_blank" href="{val}">{val}</a>'
return df.iloc[result[1]].style.format({'商品URL': make_clickable, '店舗URL': make_clickable})量子アルゴリズムによる解法（QAOA）
def futurism_solution():
simulator = Simulator()
weights = [int(data) for i, data in enumerate(df['kg'])][0:10] # Colabメモリと量子コンピュータの現在の性能上10件が限界（10件じゃなにもわからないけど許してください）
prices = [int(data) for i, data in enumerate(df['商品価格'])][0:10] # 以上同様
deduction_limit = simulator.start()
# ナップサックの場合、ものの値段等が価値で、重さによる制限がある。今回の場合、ものの重さを価値として、値段の制限がある。
knapsack_problem = KnapsackProblem(values=weights, weights=prices, max_weight=deduction_limit)
result = knapsack_problem.solve_by_qaoa()
print(f'控除上限額は{deduction_limit}円')
HTML(df.to_html(render_links=True, escape=False))
def make_clickable(val):
return f'<a target="_blank" href="{val}">{val}</a>'
return df.iloc[result].style.format({'商品URL': make_clickable, '店舗URL': make_clickable})実行
実用的な解法の結果（控除上限額以内で重いものを選択してくれています）
practical_solution()
量子アルゴリズムによる解法の結果（実行開始から終了まで30分~1時間かかります）（控除上限額以内で重いものを選択してくれています）
futurism_solution()
