3つの倍数を組み合わせて余りを最小にする計算

質問

ある数Xがあり、それを3つの数A、B、Cの倍数を組み合わせてXの値に近づける時、
A、B、Cそれぞれに掛ける数を導くにはどのような計算でできますか？

例えば300というXがあり、20、30、50と言う3つの数が用意されている場合、
20x1+30x1+50x5=300になりますが、それぞれの数を何倍にすれば300に最も近い数字をだすには、どういった計算が可能でしょうか？

解りにくい質問ですが、何卒よろしくお願い致します。

回答No.4

178-tall

300 と 20, 30, 50 の例ならば、{20, 30 ,50} を最大公約数 10 で割った {2, 3, 5} を係数とし、300/10 = 30 を帰結とする「一次不定方程式」、
　2*X + 3*Y +5*Z = 30
「互除法」などで解け、一般解を羅列可。

「一次不定方程式」からの連想的予測では、帰結値が係数たちの最大公約数で割り切れる場合 (つまり、係数たちは互いに素である場合) ならピタリと解けそう。

この予測？があってれば、帰結値を係数の最大公約数で割ったときの剰余が最少となる値が「最も近い数字」になりそうですが、さて？

回答No.3

tadys

倍数として負の数を使わないとします。

Xを（A+B+C）で割ってみます。
余りが出なければ、それで最適解が求まります。
余りが出たなら、余りをA、B、C、（A+B）、（A+C）、（B+C）で割ります。
このあまりのうち一番小さいものをA、B、Cで割っていちばん余りが小さくなったものが多分求める組み合わせです。
確かめていないので間違っているかもしれません。

回答No.2

Tacosan

究極は動的計画法

回答No.1

nag0720

倍数とは、０倍や－１倍なども認める？

例の場合、20x1+30x1+50x5=300　以外にもいろいろな答（20x7+30x2+50x2=300など）があるが、どれがより望ましいというのはあるのか。

整数の問題だから、計算式を立ててスパッと答が出るのいうわけにはいかないでしょうね。
例えばユークリッドの互除法のような、ある程度のアルゴリズムが必要になるでしょう。