Detailed explanation of the homework is below. Thanks in Advance
A Prolog program for the following problem:
We have n boxes B1, B2, …, Bn. Each box Bi has capacity Ci that indicates the number of kilograms that the box can carry. We have m objects O1, O2, …, Om. The weight of an object Oi is denoted by Wi. The total weight of the objects (i.e. W1+W2+…+Wm) is greater than the total capacity of the boxes (i.e. C1+C2+…+Cn). The problem is putting the objects into the boxes such that the total weight of objects in the boxes is maximized as much as possible.
For instance, let n=2, m=5, (C1=10, C2=20), (W1=6, W2=8, W3=25, W4=2, W5=19). The optimal solution will be “put O2 and O4 into B1 and put O5 into B2”.
To find the optimal solution, normally we need to follow a search strategy that searchs the state space exhaustively. That is, the strategy considers all possible assignments of objects to boxes and chooses the best one. We know that exhaustive search is very time-consuming. So, in this project, we will aim at solving this problem using heuristic search.
Decide on a knowledge representation for this problem. That is, decide on which predicates you will use and what will be the state space representation.
Write a Prolog program that uses a heuristic to solve this problem. Implement the heuristic as a predicate that, given a state as input, returns the value of the state. Think about at least three different heuristics and solve the problem with each one. Devise at least five test cases with different values for the parameters of the problem (n, m, Ci and Wi).
Test the program with the test cases and using different heuristics for each one. The output of an execution must include sufficient information to understand how the problem was solved. It must show the alternative choices at each step and the backtracking points.
• Your project will be graded on correctness, readability, testing strategy, efficiency, and the use of logic programming style.
• You must use pure logic programming style. That is, you may not use the operators and predicates like ; (“or”), -> (“if-then”), and “repeat”. An exception is that you may use the ! (cut) predicate.