JaCoP：解決0/1揹包問題

Question

我一直在試圖教自己如何使用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); 

我加入使用揹包列表揹包約束：

約束CON =新的揹包（揹包， 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"); 
} 

結果我得到的是簡單，所有的數量是零，它滿足約束條件，但不優化什麼。是否還有其他約束條件或者我應該添加來嘗試並最大化每個項目的利潤*數量？

謝謝

本

Answer 1

我沒有用過Knapsack約束，但一般以優化（最小化）您使用以下（成本爲第三個參數）：

search.labeling(store, select, cost); 

請注意，這會最大限度地降低成本，因此您必須將利潤轉換爲「負成本」。示例ExamplesJaCoP/KnapsackExample.java（與ExamplesJaCoP/Example.java結合）顯示了原理。但是，該示例不使用KnapsackItem，只是普通的IntVar。