商品券が欲しい庶民の味方【第11週】プログラミング未経験者が独学成果物で「1千イイね」とれるまでリアルタイム実況
■年末年始の過ごし方
10年振り？くらいに実家で年越し。
久しぶりに実家に帰って、家族孝行が出来たのです。
それはそうと、自宅近くのスーパーで、
「年末年始のレシートで商品券が当たる！」
レシートキャンペーンをやっているわけで。
レシート複数枚合算可で3,000円分で１応募出来るとのこと。
通勤路ですから、当然レシートも貯まるわけで。
しかし、このレシート、適当に足し合わせたのでは非常に勿体ないよね。
端数は最小限にして、何とか応募総数を稼ぎたい。
■レシートキャンペーン用プログラム
結論を先に言うと、参考に出来そうな文献を見つけたのでほぼ踏襲。
パッとみて理解できてないところを補足しながら勉強中。
#Python
# coding: shift-jis
def total(numbers, target=3000):
#numbersの中の数字を組み合わせてtarget以上になる組み合わせのうちベストな組み合わせを返す
#ベストの基準: targetに近いこと、
#使用している数字の数が少ないこと、
#より小さい数字を使用していること
#該当無しの場合はNoneを返す
#もしnumbersの合計がtargetよりも小さいとき
if sum(numbers) < target:
#Noneを返す
return None
#リストを用意
res = []
#辞書を用意 {キー：バリュー}
status = {0: (0, [])}
#numbers分を繰り返す
for n in numbers:
#空のdictionaryを用意
u = dict()
for k, v in status.items():
# k+n がtarget以上の時
if k + n >= target:
res.append((k+n, len(v[1])+1, sorted(v[1]+[n])))
elif k+n not in status or status[k+n] > (v[0]+1, v[1]+[n]):
u[k+n] = (v[0]+1, sorted(v[1]+[n]))
#updateは、ある集合Aを別の集合Bで更新するメソッド
#集合Aは変化する。集合Bは変化しない。集合にはsetやdict(辞書)を使える。
#statusをuで更新
status.update(u)
return sorted(res)[0][2]
#レシートの金額（数値）を用意
numbers = [795,816,825,919,1020,1022,1144,1192,1199,1244,1328,1383,1438,1541,1652,1821]
print(numbers)
while True:
picks = total(numbers)
if picks:
print(f'{picks}, ({sum(picks)})')
for p in picks:
numbers.remove(p)
else:
print(f'残り:{numbers}')
break～計算結果～
[795, 816, 825, 919, 1020, 1022, 1144, 1192, 1199, 1244, 1328, 1383, 1438, 1541, 1652, 1821]
[795, 825, 1383], (3003)
[1192, 1821], (3013)
[816, 1020, 1199], (3035)
[919, 1022, 1144], (3085)
[1438, 1652], (3090)
[1244, 1328, 1541], (4113)
残り:[]■人の褌で相撲を取りたい
まあ、願望ですよね。楽したい。
勿論、自分で勉学するということは大事です。
しかし、このご時世、検索能力の高さは持っていたいよねって話。
ありがとう、先人！
ということで、とりあえず、計算結果から、最終組み合わせ以外を先に応募しておこう。
期間ギリギリまで買い物はするが、応募し忘れが一番痛いので、現状の最適解で一旦処理する。