いくつかの固定の数値の倍数を組み合わせてある指定の数値を得る計算式

120,610,1220,3060,4900,9000
この数の倍数を組み合わせてある指定の数値になる組み合わせ（なるべく大きい数字の倍数を増やす）を得る計算式ってありますか？
例：17500
120*3
610*4
4900*3

質問者からの補足コメント

• 

  (x*a + y*b + z*a) = 17500
  もしくは
  (120*a + 610*b + 4900*a) = x
  どちらかなら成り立たせられますか？
  x,y,zが素数になることはないです

  No.1の回答に寄せられた補足コメントです。 補足日時：2021/10/11 13:38

• 訂正
  (x*a + y*b + z*c) = 17500
  もしくは
  (120*a + 610*b + 4900*c) = x
  ですね

    補足日時：2021/10/11 13:39

No.3 ベストアンサー 回答者： neKo_deux 回答日時： 2021/10/11 15:10

「ナップザック問題」とかって種類の問題になると思います。

合計をピッタリにするのは、ちょっと変則になりますが。

Wikipedia - ナップザック問題
https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83 …


> 計算式ってありますか？

一般的には、式を解くなんかの方法では、解析的には解けません。
・動的計画法で、ある程度試行錯誤で解く。
・コンピュータの計算力に物を言わせて総当たり。
・遺伝的アルゴリズムは、合計ピッタリを探すのには向かないかも。
とか。

「ナップザック問題」のキーワードで情報収集すると、Excelのマクロとかありそう。

No.4 回答者： stomachman 回答日時： 2021/10/11 21:46

x[1],x[2],...,x[n]が小さい順に並んでいる正の数であって、「ある指定の数」をsとするとき、

　　s = k[1]x[1]+k[2]x[2]+....+k[n]x[n]
となる自然数(0を含む) k[1],....,k[n]のうちで、条件「なるべく大きい数字の倍数を増やす」を満たす解を出すアルゴリズムなら作れます。「なるべく大きい数字の倍数を増やす」順に、旨くいくまで総当たりするだけですが。

下記の A(s,x,n)は、"成功"か"失敗"か、どちらかの値を返す関数です。"成功"だった場合には、答がk[1],....,k[n]にセットされます。

A(s, x, n) =
　　もし s = 0なら
　　　　k[1]〜k[n]を全部0にする。
　　　　"成功"
　　さもなくば
　　　　mを(s/x[n])の整数部分の値にする。
　　　　もし n=1 なら
　　　　　　もし m x[n] = s なら
　　　　　　　　k[1] をmの値にする。
　　　　　　　　"成功"
　　　　　　さもなくば
　　　　　　　　"失敗"
　　　　さもなくば
　　　　　　a を"失敗"という値にする。
　　　　　　以下を(m>0 かつ a="失敗")であるあいだ繰り返す
　　　　　　　　mを1減らす。
　　　　　　　　a を A(s-(m+1)x[n], x, n-1)の値にする。
　　　　　　もし a="成功" ならば
　　　　　　　　k[n] を mの値にする。
　　　　　　　　"成功”
　　　　　　さもなくば
　　　　　　　　k[n]を0にする。
　　　　　　　　A(s, x, n-1)
終わり。

No.2 回答者： kairou 回答日時： 2021/10/11 14:15

「指定の数値」を決めないと、答えは出ないでしょう。

そして、「指定の数値」を決めたとしても、
答えが無い 場合の方が 遥かに多いと思います。

「この数」として 挙げられた 6個の数字は、全て10の倍数ですから、
「指定の数値」は 10の倍数 だけになる筈ですね。
（つまり 「指定の数値」は 少なくとも 素数にはなり得ませんね。）

又、「なるべく大きい数字の倍数を増やす」と書いてありますから、
例に挙げた 120*3+610*4+4900*3=17500 は 条件外になるのでは。

No.1 回答者： t_fumiaki 回答日時： 2021/10/11 13:31

「ある指定の数値」毎に計算式は違うよ。

また、その数値が素数だったら組み合わせなんか出来ないよ。