Question

discuss the differences and similarities (implementation and performance) between the solution for 0-1 knapsack problem using Backtracking versus Branch and Bound. Do not just define the algorithms compare the performance and implementation of the 0-1 knapsack problem

Answer 1

We can use Backtracking to optimize the Brute Force solution. In the tree representation, we can do DFS of the tree. If we reach a point where a solution no longer is feasible, there is no need to continue exploring. Backtracking would be much more effective if we had even more items or a smaller knapsack capacity.

The backtracking based solution works better than brute force by ignoring infeasible solutions. We can do better (than backtracking) if we know a bound on the best possible solution subtree rooted with every node. If the best in the subtree is worse than the current best, we can simply ignore this node and its subtrees. So we compute-bound (best solution) for every node and compare the bound with current best solution before exploring the node.

Branch and bound is a very useful technique for searching a solution but in the worst case, we need to fully calculate the entire tree. At best, we only need to fully calculate one path through the tree and prune the rest of it.