Semantic and Declarative Technologies Course, Homework C2, some hints
This page gives some hints on the predicate knapsack/4 of Homework C2.
Consider the example below:
| ?- Items = [item(1,3,4),item(2,8,6),item(3,7,7),item(4,1,5)],
knapsack(Items, 10, 10, Selected).
The task of the knapsack goal can be decomposed into the
following steps:
- extract the lists of item weights
[3,8,7,1] and item
values [4,6,7,5] from Items
-
Here is an example of a similar extraction task: given a list
of
Key-Value pairs return the list of Values:
pairs_values/2
Remember that Key-Value is the same as -(Key,Value).
- create a list of 0-1 variables of the same lengths as
Items
- post the constraint that the total weight should be =< 10
- post the constraint that the total value should be >= 10
- do labeling
- create output: extract the list the selected item ids from
Items
Last modified by Péter Szeredi,
szeredi@cs.bme.hu,
on 04-16-2023.