JaCoP : 0/1 배낭 문제 해결

Question

저는 JaCoP 제약 프로그래밍 라이브러리를 사용하는 방법을 스스로 가르쳐 왔지만 0/1 배낭 문제를 구현하는 데 어려움이 있습니다. ,

제약 사기꾼 = 새로운 배낭 (배낭 :

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); 

내가 다음 배낭 목록을 사용하여 배낭 제약 조건을 추가 한 다음과 같이 나는 항목과 변수를 4 문제의 크기를 시도하고 정의한 배낭 용량, 배낭 배율); 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"); 
} 

내가 얻는 결과는 모든 수량이 제약 조건을 만족하지만 아무것도 최적화하지 않는, 제로 것을 단순히 :

는 그리고 난 후 튜토리얼에 주어진 방법으로 해결책을 검색 한 . 각 품목에 대해 이익 * 수량을 극대화하기 위해 추가해야하는 또 다른 제약이 있습니까?

당신에게 내가 Knapsack 제약 조건을 사용하지 않은

Answer 1

벤 감사하지만, 일반적으로 사용하는 다음 (세 번째 인수로 비용을) 최적화 (최소화)하기 :

search.labeling(store, select, cost); 

이렇게하면 비용이 최소화되므로 이익을 "마이너스 비용"으로 변환해야합니다. 예 : ExamplesJaCoP/KnapsackExample.java (ExamplesJaCoP/Example.java과 결합)은 원칙을 보여줍니다. 그러나이 예에서는 KnapsackItem을 사용하지 않고 단지 IntVar 만 사용합니다.