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

Я затем добавил ограничение ранца с использованием списка рюкзака:

Constraint 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.