JaCoP: решение проблемы ранца 0/1 - PullRequest
Новая
       19

JaCoP: решение проблемы ранца 0/1

1 голос
/ 29 ноября 2010

Я пытался научить себя, как использовать библиотеку программирования ограничений 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Рюкзак (ранец, рюкзак, емкость, рюкзак, профит);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");
}

В результате я получаю просто то, что все величины равны нулю, который удовлетворяет ограничениям, но ничего не оптимизирует.Есть ли другое ограничение или что-то, что я должен добавить, чтобы попытаться максимизировать прибыль * количество для каждого предмета?

Спасибо

Бен

1 Ответ

2 голосов
/ 29 ноября 2010

Я не использовал ограничение Knapsack, но в целом для оптимизации (минимизации) вы используете следующее (стоимость в качестве третьего аргумента): 

search.labeling(store, select, cost);

Обратите внимание, что это минимизирует стоимость, поэтому вы должны конвертировать прибыль в «отрицательную стоимость». Пример ExamplesJaCoP/KnapsackExample.java (в сочетании с ExamplesJaCoP/Example.java) показывает принцип. Однако в примере не используется KnapsackItem, просто IntVar.

...