

顧客から商品の購入依頼があります。  
その商品を最適なセット商品の購入に変更して、最安の値段で購入したいです。  
よいアルゴリズムがあれば教えていただきたいです。

例）  
顧客からの購入依頼  
商品A 20個 単価200円 合計金額4000円  
商品B 10個 単価300円 合計金額3000円

セット商品  
商品ABセット 金額 450円  
内訳  
商品A 1個  
商品B 1個

上記の場合、顧客が購入するものとして商品ABセットを10個購入して、商品Aを単品で10個購入するのが最適です。  
このような最適な組み合わせを選ぶ良いアルゴリズムがあれば教えていただきたいです。  
プログラムの言語は問いません。  
よろしくお願いします。

追記  
自身で調べたのですが、動的計画法を使用すれば求めれそうと思いましたがどのように適用したらよいのか分からない状態です。  
動的計画法を利用した方法でもそれ以外の方法でも良いので教えていただけると幸いです。


CC BY-SA 4.0
2022-10-23T00:06:42.377
91747
2022-11-02T22:16:11.380
2022-10-23T12:45:42.450
54974
54974
question
アルゴリズム
セット商品の最適な内訳を選択するアルゴリズムを知りたい


例題の商品を

商品A 2個 セット価格400円  
商品B 2個 セット価格600円  
商品C 2個 セット価格450円

個数を重さ、価格を価値にして、重さの総和を設定し、

0-1ナップサック問題の動的計画法を使うもので最適解が得られるのではないでしょうか。


CC BY-SA 4.0
2022-10-23T02:10:22.160
91752
2022-10-23T12:02:42.943
2022-10-23T12:02:42.943
50767
50767
91747
answer


以下の方法で求めることができました。

商品A，商品Bの顧客の依頼数： `na`, `nb`  
商品A，商品B，商品ABの単価： `pa`, `pb`, `pab`  
商品A，商品B，商品ABの購入数： `x`, `y`, `z`  
購入数での合計金額： `t`

とおくと，下記の関係があります。

[code]

    na =  1 * x +  0 * y +   1 * z
    nb =  0 * x +  1 * y +   1 * z
    t  = pa * x + pb * y + pab * z
    
[/code]

これをベクトル `n = (na, nb, t)`, `w = (x, y, z)` と行列 `A`（3x3）で表すと

[code]

    n = A * w
    w = inv(A) * n
    
[/code]

となり， `n` から `w` ，すなわち `t` から `x`, `y`, `z` を求める式が得られます。

そこで，`t` を0から徐々に増やしていき「 `x`, `y`, `z` が全て0以上の整数になる」ところを見つければ， `t` が最小となる `x`,
`y`, `z` が得られます。なお， `t` は `pa`, `pb`, `pab` の最大公約数の倍数なので， この最大公約数を単位に増やしていきます。

Python（3.9以上が必要）の実装例とその出力を示します。

[code]

    import numpy as np
    import math
    
    na, nb = 20, 10
    pa, pb, pab = 200, 300, 450
    
    A = np.array([[1, 0, 1], [0, 1, 1], [pa, pb, pab]])
    t_limit = pa * na + pb * nb
    t_step = math.gcd(pa, pb, pab)  # greatest common divisor
    
    for t in range(0, t_limit + 1, t_step):
        x, y, z = np.linalg.solve(A, np.array([na, nb, t]))
        x, y, z = round(x), round(y), round(z)
        if not pa * x + pb * y + pab * z == t:
            continue
        if x >= 0 and y >= 0 and z >= 0:
            break
    
    print(f'A: {x}, B: {y}, AB: {z}')
    print(f'Total: {t:,}')
    
[/code]

[code]

    A: 10, B: 0, AB: 10
    Total: 6,500
    
[/code]


CC BY-SA 4.0
2022-10-29T15:09:14.163
91890
2022-10-29T15:47:18.010
2022-10-29T15:47:18.010
54588
54588
91747
answer


商品A、商品B、商品ABの購入数をそれぞれ `x0`, `x1`, `x2` とすると、

[code]

    x0, x1, x2 は整数
    x0 >= 0, x1 >= 0, x2 >= 0
    1 * x0 + 0 * x1 + 1 * x2 = 20 (商品Aの購入依頼が20個)
    0 * x0 + 1 * x1 + 1 * x2 = 10 (商品Bの購入依頼が10個)
    
[/code]

という制約の下で、

[code]

    200 * x0 + 300 * x1 + 450 * x2
    
[/code]

を最小化する、という問題となります。

このような問題は、整数計画問題と呼ばれ、答えを求める汎用のライブラリが存在します。

例えば、Python-MIP を使うと、以下のように解けます。

[code]

    from mip import Model, minimize, xsum, INTEGER
    
    sets = [((1, 0), 200), ((0, 1), 300), ((1, 1), 450)]
    target = (20, 10)
    
    m = Model()
    x = m.add_var_tensor((len(sets),), "x", var_type = INTEGER)
    m.objective = minimize(xsum([p_i for _, p_i in sets] * x))
    for i, t in enumerate(target):
        m += xsum([n_i[i] for n_i, _ in sets] * x) == t
    m.verbose = 0
    m.optimize()
    print(int(m.objective.x), [int(x_i.x) for x_i in x])
    
[/code]


CC BY-SA 4.0
2022-10-30T13:01:19.750
91906
2022-11-02T22:16:11.380
2022-11-02T22:16:11.380
43506
43506
91747
answer