Given m=15

Profit: 10 10 12 18
Weight: 2 4 6 9

Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. Branch and Bound solve these problems relatively quickly.
Let us consider below 0/1 Knapsack problem to understand Branch and Bound.
Given two integer arrays val[0..n-1] andwt[0..n-1] that represent values and weights associated with n items respectively. Find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to Knapsack capacity W.

свернуть