商品券が欲しい庶民の味方【第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)
残り:[]

■人の褌で相撲を取りたい

まあ、願望ですよね。楽したい。
勿論、自分で勉学するということは大事です。

しかし、このご時世、検索能力の高さは持っていたいよねって話。

ありがとう、先人！

ということで、とりあえず、計算結果から、最終組み合わせ以外を先に応募しておこう。
期間ギリギリまで買い物はするが、応募し忘れが一番痛いので、現状の最適解で一旦処理する。

■前回