Implementing the 0/1 knapsack problem in C/C++ using the branch-and-bound method

The idea is to realize the fact that greedy methods provide the best solution to the fractional knapsack problem.

To check if a specific node can provide us with a better solution, we calculate the best solution (by node) implementing a greedy approach. If the greedy method itself computes more solutions than the best solution so far, then we cannot get to a better solution through the nodes.

The complete algorithm is as follows -

• Sort all items according to the descending order of value per unit weight ratio so that the upper limit can be calculated using the greedy method.

• Initialize the maximum profit, for example maxProfit = 0

• Create an empty queue Q.

• Decision virtual nodes create trees and insert or queue them into Q. The profit and weight of the virtual node are 0.

• Perform the following operations when Q is not empty or empty.

  • Created the project in Q. Let the extraction item be u.

  • Calculate the profit of the next level node. If the profit is higher than maxProfit, modify maxProfit.

  • Calculate the limit of the next level node. If bound is higher than maxProfit, add the next level node to Q.

  • Consider the situation where the next level node is not considered or considered as part of the solution and add the node to the queue at the level of the next level but the weight and profit are not processed Or consider the next level node.

Illustration given below -

// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10

Output

The maximum possible profit = 235

The above is the detailed content of Implementing the 0/1 knapsack problem in C/C++ using the branch-and-bound method. For more information, please follow other related articles on the PHP Chinese website!