1

基本的に、私はアイテムのリストを持っています。これには、他の多くのアイテムに最適な方法で適合する必要があるサイズと値のパラメーターがあり、可能な限り最高の値に到達しますが、maxSize 未満にとどまります。

問題を説明するには、次の説明を参照してください。

項目 1: サイズ 1、値 1;

項目 2: サイズ 2、値 4:

最大サイズ: 11; 最適なソリューション: 1xItem1、5xItem2。

しかし、まさにこの場合、制限はより高く、アイテムはより多くあります。私の問題は、可能な限り最高のミックスを見つけることです。これまでのところ、これを行うアルゴリズムを作成しましたが、複雑さが非常に悪いため、いくつかの項目でしか機能しません。

私は基本的に可能なすべての組み合わせを試しています。これにより、より多くのアイテムに対して多くの計算が作成されます。合計サイズが制限を超えるまで、パスを文字列 (Item2->Item2->Item1->Item2...) として保存しています。値が他の見つかった値よりも大きい場合は、文字列と同様に保存されます。

私がやりたいことは、すでに行われたすべての計算を保存することです。ここに例があります。

A -> A -> A -> A -> A

A -> B -> A -> A -> A

最後のケースでは、A -> A -> A を再計算する必要はありません。私がやりたいのは、それを保存することです。

これを行う最良の方法は何ですか？

現在、私の再帰は次のようになります

recursion(Item item, int size, int value, String s){
  s += cust.getName() + "-";
if(value is bigger)
  bestMix = s



for(Item item : itemList){
        if(!(we break the limit){
            recursion(item, size + item.getSize(), value + item.getValue(), s);
        }
    }
}

私がやりたいことは、再帰を行うときにすでに計算された値を取得することです。

時間の複雑さを軽減するためにこれを行うための最も簡単でスマートな方法は何でしょうか?

4

3 に答える 3

0

dasblinkenlight が言ったように、メモ化が進むべき道ですが、私は別のことをすることにしました。

私の問題は「アンバウンド ナップザック問題」と同一であることに気付きまし たwiki/Knapsack_problem

動的計画法で解決しました。 http://en.wikipedia.org/wiki/Dynamic_programming

これにより、時間の複雑さが大幅に改善されました。

于 2013-10-27T17:36:05.070 に答える
0

アイテム 1 のサイズあたりの利益 (double value/size( の 1/1 の値) があります。アイテム 2 のサイズあたりの利益は 4/2 です。そのため、 itemList ( Comparatorを使用) を最初にアイテム 2 でソートする必要があります。次に、最初の遭遇した解は最大のものになる可能性があります。

もう 1 つの改善点はint factor、すべての項目に対して、最高の係数で試してみることです。

一般に、再帰には、完了したこと、および実行すること (候補) のパラメーターがあります。

すべての呼び出しで再帰を使用すると、部分的な結果が得られます。残りを訪問する際のキャッシュは実現可能かもしれませんが、ツリー構造のような既存のデータ構造のためのものです。

于 2013-10-26T14:43:20.410 に答える