1

JaCoP 制約プログラミング ライブラリの使い方を独学で学ぼうとしていますが、0/1 ナップザック問題の実装に少し苦労しています。問題サイズ 4 を試し、項目と変数を次のように定義しました。

knapsack[0] = new KnapsackItem(quantity[0], 5, 7);
knapsack[1] = new KnapsackItem(quantity[1], 7, 9);
knapsack[2] = new KnapsackItem(quantity[2], 2, 3);
knapsack[3] = new KnapsackItem(quantity[3], 3, 3);



  IntVar knapsackCapacity = new IntVar(store, "capacity", 0, 10);
    IntVar knapsackProfit = new IntVar(store, "profit", 0, 22);

次に、ナップザック リストを使用してナップザック制約を追加しました。

Constraint con = new Knapsack(knapsack, knapsackCapacity, knapsackProfit); store.impose(con);

そして、チュートリアルに記載されている方法で解決策を検索しました。

//search for a solution and print results
Search<IntVar> search = new DepthFirstSearch<IntVar>();
SelectChoicePoint<IntVar> select = new InputOrderSelect<IntVar>(store, quantity,
           new IndomainMin<IntVar>());
boolean result = search.labeling(store, select);

if (result) {
 System.out.println("Solution: "+quantity[0]+", "+quantity[1]+", "+quantity[2]+",     "+quantity[3]);
} else {
 System.out.println("*** No");
}

私が得た結果は、すべての量がゼロであり、制約は満たしていますが、何も最適化していないということです。各アイテムの利益 * 数量を最大化するために、別の制約または追加する必要があるものはありますか?

ありがとうございました

ベン

4

1 に答える 1

2

私はKnapsack制約を使用していませんが、一般的に最適化 (最小化) するには、次を使用します (3 番目の引数としてのコスト)。

search.labeling(store, select, cost);

これによりコストが最小化されるため、利益を「負のコスト」に変換する必要があることに注意してください。例ExamplesJaCoP/KnapsackExample.java( と組み合わせてExamplesJaCoP/Example.java) は原理を示しています。ただし、この例では を使用せずKnapsackItem、単純な のみを使用していますIntVar。

于 2010-11-29T18:23:52.827 に答える