特定の合計を持つセットに数値をソートするアルゴリズム

Question

私は、18から48インチの長さの異なる27種類の硬材フローリングストリップを用意しています。私はそれぞれ3列の床で構成された3枚の板を作りたいと思います。 2枚の厚板は60インチの長さでなければならず、別の厚板は72インチの長さでなければならない。すべてのストリップの全長は、これらの厚板を構築するのに十分です。明らかに、私はランダムにストリップを選択し、それらを接着し、サイズにカットすることができました。しかし、私はカット廃棄物の量を最小限に抑えたいと思います。

この問題は、次のように簡単に書き直すことができます。27個の整数があり、それらを9個のセットにソートしたいと思います。 6つの集合のそれぞれは60まで加算され、残りの3つの集合の各々は72まで加算される。この問題は部分集合和問題の変形である。

「dynamic programming」について議論している記事がいくつか見つかりましたが、コード化する方法だけでなく、このアプローチについては何も分かりません。

similar問題が再発しましたが、議論が不足しています。

私のアプローチは「google way」です。強引な。すべてを計算する。後でそれを並べ替える。したがって、

3つの数字の9つの配列に整数をグループ化します。9！/ 3！ = 60480グループ。

各グループ 各配列の合計を計算するには、これをArraySumと呼んでください。それらのうちの9つがあります。

(A,B,C,D,E,F,G,H,I) 

（GroupSumそれを呼び出す）（72,60,60）

A-72,B-72,C-72, D-60, E-60,... 

このグループのすべての違いを追加し、その番号を保存するターゲット和との差分を計算します。これは最小化したい数値です。

入れ替えArraySumsとターゲット和のペアごとの違いは

は今、戻ってグループ化し、繰り返しを変更できます（9！/ 3！= 60480）。 私は60480 x 60480 GroupSums = 3657830400

を取得し、最も低いグループを見つけ、そのグループを選択します。

事前計算やソートよりも良い方法はありますか？

Answer 1

私は何かを誤解してきた場合を除き、それは限り、あなたはすべてで動作するグループを見つけることができるよう（つまり、すべてのグループが少なくとも必要な長さである）

ロジックがあることどのグループにそれらは無関係と思われます必要な量のストリップから始めているということです。つまり、何があってもすべてを使用する必要があります。あなたが必要とするストリップの全長は一定です（60 * 6 + 72 * 3）ので、使用する全長はどれくらいですか（あなたの27の合計はどれでも）、廃棄物は一定ですです。私が正しいことを理解しているなら、欲張りなアルゴリズムがそのトリックを行うべきです - 任意の組み合わせが、与えられた各板について最小の結果を与え、任意につなぎを解決し、次の段階に進みます。

カットする必要のあるストリップの量を最小限に抑えたい場合、つまりすべての「廃棄」をできるだけ少ないストリップに割り当てる必要がある場合を除きます。その場合は、提案したとおりにL1でなくL0損失関数を使用する必要があります。つまり、合計の値ではなく合計の数を最小にしたい場合は