Home computickets Solving the knapsack problem by the branch and bound method

Solving the knapsack problem by the branch and bound method




What is the algorithm for solving the above problem?
Wikipedia says the following:

The original algorithm, proposed by Peter Kolesar in 1967, suggests sorting items by their unit cost (value-to-weight ratio) and building a brute-force tree. Its improvement lies in the fact that in the process of building a tree, for each node, we estimate the upper bound on the value of the solution, and continue to build the tree only for the node with the maximum estimate [10]. When the maximum upper bound is in the leaf of the tree, the algorithm ends.

What is a brute-force tree?

What is the upper bound on the value of a solution?

What is the general algorithm for solving the knapsack problem in this way? Code or pseudocode for solving this problem will be useful

Answer 1, authority 100%

In simple terms, then:

We have a node, this is our current state, i.e. the number of items that are currently in the backpack. We also have branches, these are connecting paths to other nodes (states), i.e. as if we are putting one thing in a backpack.

Let’s say we have an empty backpack with a carrying capacity (5kg) and we need to put: a laptop (2kg), a sleeping bag (3kg), a hammer (5kg).

Then the exhaustive search tree will look like this:

In this tree, we can notice that we have nodes that exceed the weight of the backpack and at the same time they also have descendants, but why should we continue to consider the following options if it only gets worse? Therefore, we restrict the weight to 5 and get the following graph:

At the output, we get that there are 2 options, either we put it in a backpack: a laptop and a sleeping bag, or a hammer.

Depending on the implementation, you can search for all options, the first one or set additional optimality criteria.

Programmers, Start Your Engines!

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.

Recent questions