特定の値の倍数で合計を計算するアルゴリズム

Question

数値の部分集合の倍数を使用して、その合計に対する既知の合計または最も近い値を計算しようとしています。このアプローチでは、倍数または係数を最小限に抑えたいと考えています。私は数120を持っていると私は50sと20sのセットを持っている場合、私は唯一の1x50と6x20sを持っているので、もし、私は数字のセットが、しかし

120 = 2*50 + 1*20. 

を制限することが可能になるだろう。例えば

、私は5x20sを持っている場合、私は、私は、係数を最小限にしたいから、私は

を持つことになり、さらに

120 = 6*20. 

を取得します

110 = 1*50 + 3*20. 

この場合、値は合計に最も近い値であることに注意してください。合計が達成できれば、それはより少ない倍数で合計に最も近い値を持つことよりも優先されます。

この結果を得るための既知のアルゴリズムはありますか？

Answer 1

あなたが求めるアルゴリズムは、しばしば「貪欲」アルゴリズムと呼ばれます。理論について、その仕組みについて読むことができます。Cut optimisation algorithm

一般的な使用例は、製造時に使用されるカット長の最適化です。マクロとしてスクリプト化アルゴリズムを使用して、このスプレッドシートを試して、この動作の例についてはhttps://en.m.wikipedia.org/wiki/Cutting_stock_problem

：問題を論じ、このWikipediaの記事、および必要に応じて最適化アルゴリズムの背後にある計算をチェックhttp://www.cutoptimizer.com