Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
@yuki07770
Revisions
Report this question
Subscribe question
Help us understand the problem. What is going on with this question?
Q&A

2つの数字を組み合わせて目的の値を作りたい。

解決したいこと

目的の値と一致する組み合わせを探したい

例)
Pythonを使ってナップザック問題のようなものを解決したいです。
売り上げが510円とします。
商品は2種類(将来的には5種類まで増やしたい)
商品A:単価100円
商品B:単価30円と仮定します。

510円はAとBが何個売れたか知りたいです。
(一致がさせたい)
毎月変動するので、他にも870円なら?1060円なら?と増やしていきたいです。

今までやったこととしては、ナップザック問題はいくつか見ながら解きました。
例えば
名前:重さw(kg):価値p(円)として、
ものa:重さ1:価値:10
ものb:重さ2:価値14
ものc:重さ6:価値35
ナップザックの重さは10kgを超えない最適な組み合わせの個数(N)は?
という問題が多くありました。これは一番近いことができるように見えて、要素不足で諦めました。
わたしの場合、個数(N)が求めたいのですが、重さに該当する式がありません。
価値を最大化するための要素として、重さwの式が足りないので式の組み方がわかりませんでした。

Q1.わたしの希望する510円の組み合わせの式は難しいことなのでしょうか?

発生している問題・エラー

続いて、リスト1内にAの倍数になるもの、リスト2にBの倍数となるもの

list1[100,200,300,400,…]
list2[30,60,90,120,150,…]
というのを作成し、それぞれを組み合わせて目的の510円になる組み合わせを探すことも考えました。
しかしこれは、作成した組み合わせから510を見つけてもらったときに、何と何を足して510になったか教えてもらうことができず、数えてやりましたが、今後は数えなくてもわかるようにしたいです。
Q.2ここも何か解決策ありますか?

続いて、計算速度を下げるためと上記の何と何の足し算なのかわからないという問題を解決するために、商品AとBのひょうを作ろうかと考えました。そこから、使った数字を返してもらう方法です。
しかし、これも難しそうで、コードの例が見つかりません。
例-表)
1 2 3 …
商品A 100 200 300 …
商品B 30 60 90 …
と、なったときに、160が目的として、その組み合わせ100+60ならば、Aの1ことBの2こが答えとなりますので、A=1 B=2といった返しが欲しいのですが、
Q3.これも難しいでしょうか?

Excelでソルバーを使っていましたが計算があまりにも遅く、1つをやるのに1時間程度かかっていました。パソコン本体のスペックが関与していると思います。

Q4.そのパソコンを変えずに、2商品の組み合わせを見つける方法を教えてください。

また、難しいことがわかったら諦めて、総当たり表を作ろうかと思います。商品は最終的には5種類、数の上限は80になるので、総当たり表を作ることは正直現実的ではありませんが、3ヶ月悩んで調べたのですが、3ヶ月前にPythonの名前を聞いたレベルの人間なので、まだまだ調べ方が足りないのでは?とおもっています。

もし、ご存知の方がいましたら教えてください。他のやり方でも、オススメの方法でも。
よろしくお願いします。。

自分で試したこと

ここに問題・エラーに対して試したことを記載してください。

0
2
Answer

機械学習は学んでいないのですが考え方の一助になればと思い記します。

例示のケースですと、売上の求め方は
30×α個+100円×β個=売上
となります。

販売総数は次の式で求められます。
α+β=販売総数

例のケースは300円とのことなので解きます。

因数分解します。
2×5×(3×α+2×5×β)=2×2×3×5×5

両辺を2×5で割ります
3×α+2×5×β=2×3×5

2、3、5が両辺にあるのが分かると思うのですが、
この時に何がいくつ売れたか知る為に必要なものは販売総数だけです。
販売総数が分からない場合は計算できないかなと思います。

下記の式をぱっとみたときに、
3×α+2×5×β=2×3×5

αに2×5が入れば等しくなる(β=0)
βに3が入れば等しくなる(α=0)
ということが何となく見た感じでわかるかと思います

αがとる値は最小0、最大10
βがとる値は最小0、最大3
となります。

本当でしょうか?
端折らずに解きます。

まず下記の式をα=になるように解いていきます。
※2×5×βを移項して両辺を3で割って共通項2×5で括ります
3×α+2×5×β=2×3×5
3xα=2×3×5-2×5×β
α=2×5-2×5×β/3
α=2×5(1-β/3)

αは整数であり、右辺もまた整数である必要があります。
1-β/3の部分が整数になるには、
βが3の倍数出ないといけないことが分かります。
候補 0、3のみ。

こんどは下記の式をβ=になるように解いていきます。
※3×αを移項して両辺を2×5で割って共通項3で括ります
3×α+2×5×β=2×3×5
2×5×β=2×3×5-3×α
β=3-3×α/2×5
β=3×(1-α/2×5)

βは整数であり、右辺もまた整数である必要があります。
1-α/2×5の部分が整数になるには、
αが10の倍数出ないといけないことが分かります。
候補 0、10のみ。

上記の計算により、
αとβの候補は上がりましたが…
同時に0の場合はそもそも売り上げが上がらず、
3と10を取ると売り上げが600円になってしまうことから、

α=10、β=0またはα=0、β=3
ということが分かります。

どちらが売れたかを特定するには、
α+β=3?
α+β=10?
どっちか教えてくれないと分からないよ?

ということで、以上証明終わりです。Q.E.D

0
回答ありがとうございます。
証明助かりました!
因数分解のこういう手は思いつきませんでした。
今回の最終の最終は商品は5種類で、商品単価のケタ数は7桁を想定しているので、1回チャレンジしてみます。

過去に、5種類の品物のうちどれが売れたかだけでもわかればと思い、因数分解をしてみたことがあります。Excelのソルバーを元々使っていて、計算速度が遅過ぎたことから諦めましたが、商品数が減れば計算する量が減ると感じたため。
(因数分解と素因数分解の違いがわかっていないため間違った表現かもしれませんが)
特徴的な素数があれば特定できるかもと思いましたが、これはダメだと思っていました。理由は品物商品A100→2,2,5,5
翔B30→2,3,5となり、3があればBが売れたということになるのか?と思いやってみたのですが、
Aが1こBが2この場合160→2,2,2,2,2,5となり、3が消えてしまう…というのが問題となり、特定できないと感じていましたが、今回説明してもらったようなやり方で望めば、できるのかもしれないと思っています。

ありがとうございました!
もし、他のやり方をご存知でしたらご教示願います。

よろしくお願いします。!
総当たりを試されるようなので、
お茶飲みながら休憩しつつ結果を待つ。
とかでも良いのかなと思います。

もし多少時間を短くするとしたら、
まず売上理論値の上限と下限を求めます。
30円×80個=2400円
100円×80個=8000円

上記の条件の場合、
売り上げが2410円を超える場合は、
必ず100円のモノが1つ以上売れている必要があるとか、
下2桁が00の時は30円のものは10個単位で売れてるとか、
下2桁が00以外の時は30円のモノが1つ以上必ず売れているとか。
考えるとちょっとややこしいですけどね。

例えば2410円なのであれば、
30円×80個=2400円を超えているので、
100円が1つ以上必要になります。
100円を1つ増やして、30円を1つ減らすと70円増えます。
2470円で2410円を60円上回ってしまうので、不成立。
みたいなやり方ですかね。

総個数が固定されているとき、
αを減らして、βを増やすと、αとβの差額分が増減します。

5620円みたいな数字が出た時は、
30円を40個、100円を40個とまず半分ずつでアタリをつけ、
1200円+4000円で5200円なので420円足らない。
100円の数を増やせば差額の70円ずつ増えるので、
420円割る70円で6個30円を減らして6個100円を増やす。

30円×34個=1020円
100円×46個=4600円
計5620円でこの売上なら成立する。

こんな感じでしょうか。

考え方のポイントは、
1.種類毎の売上理論値の上限を求めること。
2.商品毎の差額を出すこと。
3.商品が均等で売れた場合の平均売り上げを出し、
実際の売り上げが上ならば高い商品を増やして総当たり、
実際の売り上げが下ならば安い商品を増やして総当たり。

3をすると総当たりの数を半分くらいに出来るんじゃないかなぁと。

サイコロを5つ振った時に最低値は5、最高値は30
5に近ければ1,2,3の割合を増やし、
30に近ければ4,5,6の割合を増やす。

半分の16以上が出た場合は3×5=15で1~3まででは成立しないので、
総当たりを半分に削れる…

みたいな考え方です。

総当たりで実施されるとのことで、
多少でも時間が減らせれば良いかなと思いお伝えしました。
ちょっとまとまりが無いですが、ご笑覧下さいませ。
ではでは。
View the remaining 1 comments.

合計値を一致させたいのであれば最適化問題ではないですね。多分最適化問題と同じアプローチでも行けるとは思いますが若干遠回りになる気がします。

とりあえず単純に総当りで解くのを作ってみました。2商品程度であればこれでも一瞬でしたが、最悪ケースの5商品80個の総当たりは数分くらい時間かかったのでマルチプロセスするか候補をうまく絞るか他の言語を使うが次の選択肢になると思います。

target_total = 510
a_max = target_total // 100
b_max = target_total // 30
# +1 for inclusive iteration
xs = ((aq, bq) for aq in range(a_max+1) for bq in range(b_max+1) if aq*100+bq*30==target_total)

print(f"quantities where total={target_total}:")
for aq, bq in xs: print(f"  a={aq}, b={bq}")
0
ご回答ありがとうございます。
できました!完璧です!!
5商品で試してみました。数分かかりましたが、今までエクセルのソルバーで1時間以上かかっていたものが数分なので満足です。

最適化は似て非なるものだったのですね。ずっと遠回りしていました。
今後ご提案いただいたマルチプロセスや、候補を絞る方法、他の言語も検討してみます。
もしお勧め言語があれば教えていただけませんか?計算をするのはPythonが一番良いと思い選んだ言語でした。Cとかでしょうか??
Cは配列の取り扱いがだいぶ難しいので、速度必須なプログラムであればC++かRustをおすすめします。
あるいはPythonに似た書き心地で高速な言語でJuliaというのもあるので、そちらも触ってみると良いかと思います。
ありがとうございます。速度は今のところ必須ではないのですが、今後を見越してスピードアップも検討します。C++は将来的に候補に入っていたので見てみます。
Juliaは初めて聞きましたが、触ってみます。
ありがとうございました。
View the remaining 2 comments.
Help us understand the problem. What is going on with this answer?
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login