よちよちpython

独習 python/Qpython/Pydroid3/termux

予算内で複数の品物の数量をみつくろうプログラム

「お菓子は500円までです。」
「焼き鳥の串を持ち帰りで3000円分適当にみつくろってよ」
「予算が余ったんで消耗品を頼む。数量は任せる。赤ボールペンと、マジックと、バインダーと、ガムテープと…」



決まった予算内で何の品物をどれだけ買えるか、という場面に遭遇したらどうしてますか。条件が込み入って来ると意外と計算が面倒です。
Pythonで自動的に出させてみます。



想定

単価の明らかな5品からそれぞれの数量を決定し、トータル金額を予算30000円内に押さえる問題です。
数量はなるべく同じぐらいになるようにしたい。

単価のリスト


5品の単価をリストで書きます。商品名は無視します。

# 単価のリスト(税込み
pl = [198,120,5000,357,430]

各数量をランダムで出す


5品の各数量をランダムで出します。Numpyを使います。
数量はとりあえず1以上20以下にしましょうか。

import numpy as np

# 1以上20以下の整数をランダムに5個だす
x = np.random.randint(1,21,5)
x
array([ 6, 20, 11,  8, 10])

1~20までのランダム値が5個でました。



トータル金額の算出


予算内に押さえる為に、単価×数量を算出します。
Numpyを使うと、Numpy配列同士(またはどちらか一方)の掛け算は各要素同士がそのまま掛けられます。

# トータル金額
total = sum(pl * x)
total
65744

はい、3万円の予算をオーバーしてしまいました。トータル金額が予算内に収まるように、次にifでしぼります。

と、その前に、リスト同士を単に掛けるとどうなるか試しておきます。

lst1 =  [1,2,3]
lst2 = [4,5,6]

print(lst1 * lst2)
----------------------------------------------

TypeError    Traceback (most recent call last)

<ipython-input-10-512d693c8890> in <module>
      2 lst2 = [4,5,6]
      3 
----> 4 print(lst1 * lst2)


TypeError: can't multiply sequence by non-int of type 'list'

単にリストを掛けると上のようにエラーになります。
forで各要素を1つずつ取り出して掛けるようにする。↓

lst1 =  [1,2,3]
lst2 = [4,5,6]

# 内包表記
print([i*j for i,j in zip(lst1,lst2)] )    
[4, 10, 18]

面倒ですね。Numpyを使う方が早いです。



予算内におさえる


できれば予算3万円に限りなく近い方が良いので、29990円以上30000万円以下になるように条件を設定します。

if 29990 <= total <= 30000:

トータル金額がこの条件に当てはまった場合、リストなどに格納するようにします。
空のリストを用意しておいて、条件を満たせばそれをappend()で追加していきます。

# トータルと数量をリストに追加
lst.append([total,x])
# 試行カウンターに1を足す
cnt += 1



上記をループ


  • ランダムな個数取り出しを何回試行させるかをwhileでループさせます。
    • 試行の初期値をゼロ、
    • 試行が一回終わるとカウンターに1を加える。
    • 試行回数が設定を満たせばループを抜ける。

ここまでをまとめて書きます。
1000回ループさせてみます。

import numpy as np

# 単価のリスト(税込み
pl = [198,120,5000,357,430]

# 
lst = [] #条件を満たしたデータ格納庫
cnt = 0 #カウンター初期値

# ループ
while cnt < 1000:
    # 1以上20以下の整数をランダムに5個だす
    x = np.random.randint(1,21,5)
    # トータル金額の算出
    total = sum(pl * x)

    # 予算内かどうか
    if 29990 <= total <= 30000:
        # 満たせばリストに追加
        lst.append([total,x])
    
    # 試行カウンターに追加
    cnt += 1
        
# 条件を満たしたデータリストの表示
print(lst)
[]

一瞬で1000回試行し終わったが、リストは空のまんま。何度か実行すると取れることは取れる。
カウンターに1追加する文のインデントの位置を間違うとループが止まらなくなるので注意します。そうなったらターミナル実行でならCtrl+cで。Jupyter Notebookならボタン。

次は試行を1万回に増やしてみる。

import numpy as np

# 単価のリスト(税込み
pl = [198,120,5000,357,430]

# 
lst = [] #条件を満たしたデータ格納庫
cnt = 0 #カウンター初期値

# ループ
while cnt < 10000: #1万回に書き換えた
    # 1以上20以下の整数をランダムに5個だす
    x = np.random.randint(1,21,5)
    # トータル金額の算出
    total = sum(pl * x)

    # 予算内かどうか
    if 29990 <= total <= 30000:
        # 満たせばリストに追加
        lst.append([total,x])
    
    # 試行カウンターに追加
    cnt += 1
        
# 条件を満たしたデータリストの表示
print(lst)
[[29999, array([11,  5,  4, 13,  6])], [29994, array([16,  8,  4,  8,  7])]]

1万回も試行して、たったの2つ。このやり方は効率が悪いんだろう。



品物の個数を同じぐらいにする


「適当に数量をみつくろ」う要求は「大体同じぐらいに」にしておけば間違いない。要求に応えるには、ランダムな個数の取り出しに更なる条件を追加しなくてはなりません。
それには「集合がどれくらいバラついているか」を示す標準偏差 を利用します。
標準偏差は、バラつきが無いほどゼロに近づきます。全部同じならゼロになります。バラつきの大体の目安になる。

Numpyで出すにはnp.std(リスト)を使います。ちょっと試します。

# リスト1
l_1 = [567,567,567,567]
print(l_1)
# 標準偏差の算出
print(np.std(l_1))

print("-"*20)

# リスト2
l_2 = [24, 58, 100, 7, 69]
print(l_2)
# 標準偏差の算出
print(np.std(l_2))

[567, 567, 567, 567]
0.0
--------------------
[24, 58, 100, 7, 69]
32.97635516548183

リスト1は全て同じ数値なので標準偏差はゼロになっていますが、リスト2はバラついているため値も大きく出ています。



先ほどまでのループプログラムに、標準偏差の値を組み込んでみます。

import numpy as np

# 単価のリスト(税込み
pl = [198,120,5000,357,430]

# 
lst = [] #条件を満たしたデータ格納庫
cnt = 0 #カウンター初期値

# ループ
while cnt < 10000: 
    # 1以上20以下の整数をランダムに5個だす
    x = np.random.randint(1,21,5)
    # トータル金額の算出
    total = sum(pl * x)
    # 個数の標準偏差
    x_std = np.std(x)

    # 予算内かどうか
    if 29990 <= total <= 30000 and x_std < 5 :
        # 満たせばリストに追加
        lst.append([total, x, x_std])
    
    # 試行カウンターに追加
    cnt += 1
        
# 条件を満たしたデータリストの表示
print(lst)
[[29999, array([14,  6,  4, 11,  6]), 3.7094473981982814]]

標準偏差を「トータル金額の算出」の下と、if文の条件と、append()の引数の3ヶ所に追記しました。
実行すると1つしか出てきませんでした。条件が厳しすぎたのか。

下手な鉄砲、数撃ちゃ当たる。一気に10万回ブン回してみる。

import numpy as np

# 単価のリスト(税込み
pl = [198,120,5000,357,430]

# 
lst = [] #条件を満たしたデータ格納庫
cnt = 0 #カウンター初期値

# ループ
while cnt < 100000: 
    # 1以上20以下の整数をランダムに5個だす
    x = np.random.randint(1,21,5)
    # トータル金額の算出
    total = sum(pl * x)
    # 個数の標準偏差
    x_std = np.std(x)

    # 予算内かどうか
    if 29990 <= total <= 30000 and x_std < 5 :
        # 満たせばリストに追加
        lst.append([total, x, x_std])
    
    # 試行カウンターに追加
    cnt += 1
        
# 条件を満たしたデータリストの表示
print(lst)
[[29993, array([ 8, 17,  4,  7,  9]), 4.33589667773576], [29991, array([1, 6, 5, 9, 2]), 2.8705400188814645], [29999, array([11,  5,  4, 13,  6]), 3.54400902933387], [29994, array([ 7,  5,  4, 14,  7]), 3.4985711369071804], [29993, array([ 8, 17,  4,  7,  9]), 4.33589667773576], [29996, array([13,  1,  4,  6, 12]), 4.621688003316537], [29994, array([10,  6,  4, 12,  7]), 2.85657137141714]]

試行回数を増やすと計算時間が掛かる。8秒ぐらい。もう少し条件を絞ります。
ランダムな個数の範囲を(1以上11未満)に減らし、試行2万回ループ。

import numpy as np

# 単価のリスト(税込み
pl = [198,120,5000,357,430]

# 
lst = [] #条件を満たしたデータ格納庫
cnt = 0 #カウンター初期値

# ループ
while cnt < 20000: 
    # 1以上10以下の整数をランダムに5個だす
    x = np.random.randint(1,11,5)
    # トータル金額の算出
    total = sum(pl * x)
    # 個数の標準偏差
    x_std = np.std(x)

    # 予算内かどうか
    if 29990 <= total <= 30000 and x_std < 5 :
        # 満たせばリストに追加
        lst.append([total, x, x_std])
    
    # 試行カウンターに追加
    cnt += 1
        
# 条件を満たしたデータリストの表示
print(lst)
[[29994, array([1, 9, 5, 8, 2]), 3.1622776601683795], [29996, array([ 2,  5,  5, 10,  1]), 3.1368774282716245], [29999, array([4, 7, 5, 1, 7]), 2.227105745132009], [29993, array([5, 3, 5, 9, 1]), 2.65329983228432], [29999, array([ 8, 10,  5,  5,  1]), 3.059411708155671]]

この辺の調整は好きにイジるとして、一応「3万円予算に近い金額で、数量もそこそこバラつきの少ない感じで」すぐに見積りが出せることはできた。

あとは、

  • 「品物によっては数量指定され、残りを帳じり合わせする場合」とか、
  • 「予算を分割された場合」とか、
  • 思い付く限りの条件に応じられるようにするとか、
  • Excelに組み込む」とか、
  • 「利益率の高い品物の数量は多めになるようにする」

などすれば、結構現場で重宝するんじゃないでしょうか。



参考リンク


標準偏差の意味と分散との違い | 高校数学の美しい物語



おわりに


YouTubeにExcelVBAの使い方を分かりやすく投稿されているこいこいさんという方がいらっしゃいまして、その中にExcelからPythonを呼び出して遺伝的アルゴリズムで勤務シフト表を作るシリーズもの、陸上部のチーム編成ものがある。qiitaなんかに投稿された遺伝的アルゴリズムの解説はガチな数学的説明で非常に難しいんですけど、こいこいさんのプログラムはPandasとNumpyだけで作ってあり、難解ではなく、とても面白い。
で、今回やったようなことをもう少し計算を減らそうとするなら、遺伝的アルゴリズムのようになるんだろうなぁと思ってこれを書いた次第でございました。

追記
商品点数5点で数量が1~10のどれかなら、組み合わせは105=10万(10*10)5=100億通り。数量が1~20なら組み合わせは205=320万(20*20)5=10兆2400億通りか?これくらいならランダムより全組み合わせを総当たりした方がいいのかな?無駄か?
総当たりは無理げ。



以上です。