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。