We discussed different approaches to solve above problem and saw that the Branch and Bound solution is the best suited method when item weights are not integers.
In this post implementation of Branch and Bound method for 0/1 knapsack problem is discussed.
How to find bound for every node for 0/1 Knapsack?
The idea is to use the fact that the Greedy approach provides the best solution for Fractional Knapsack problem.
To check if a particular node can give us a better solution or not, we compute the optimal solution (through the node) using Greedy approach. If the solution computed by Greedy approach itself is more than the best so far, then we can’t get a better solution through the node.
Complete Algorithm:
- Sort all items in decreasing order of ratio of value per unit weight so that an upper bound can be computed using Greedy Approach.
- Initialize maximum profit, maxProfit = 0
- Create an empty queue, Q.
- Create a dummy node of decision tree and enqueue it to Q. Profit and weight of dummy node are 0.
- Do following while Q is not empty.
- Extract an item from Q. Let the extracted item be u.
- Compute profit of next level node. If the profit is more than maxProfit, then update maxProfit.
- Compute bound of next level node. If bound is more than maxProfit, then add next level node to Q.
- Consider the case when next level node is not considered as part of solution and add a node to queue with level as next, but weight and profit without considering next level nodes.
Illustration:
Input:
// First thing in every pair is weight of item
// and second thing is value of item
Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},
{5, 95}, {3, 30}};
Knapsack Capacity W = 10
Output:
The maximum possible profit = 235
Below diagram shows illustration. Items are
considered sorted by value/weight.
Note : The image doesn't strictly follow the
algorithm/code as there is no dummy node in the
image.
This image is adopted from here.
Following is C++ implementation of above idea.
[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20solve%20knapsack%20problem%20using%0A%2F%2F%20branch%20and%20bound%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Stucture%20for%20Item%20which%20store%20weight%20and%20corresponding%0A%2F%2F%20value%20of%20Item%0Astruct%20Item%0A%7B%0A%20%20%20%20float%20weight%3B%0A%20%20%20%20int%20value%3B%0A%7D%3B%0A%20%0A%2F%2F%20Node%20structure%20to%20store%20information%20of%20decision%0A%2F%2F%20tree%0Astruct%20Node%0A%7B%0A%20%20%20%20%2F%2F%20level%20%20–%3E%20Level%20of%20node%20in%20decision%20tree%20(or%20index%0A%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20%20in%20arr%5B%5D%0A%20%20%20%20%2F%2F%20profit%20–%3E%20Profit%20of%20nodes%20on%20path%20from%20root%20to%20this%0A%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20node%20(including%20this%20node)%0A%20%20%20%20%2F%2F%20bound%20—%3E%20Upper%20bound%20of%20maximum%20profit%20in%20subtree%0A%20%20%20%20%2F%2F%20%20%20%20%20%20%20%20%20%20%20%20of%20this%20node%2F%0A%20%20%20%20int%20level%2C%20profit%2C%20bound%3B%0A%20%20%20%20float%20weight%3B%0A%7D%3B%0A%20%0A%2F%2F%20Comparison%20function%20to%20sort%20Item%20according%20to%0A%2F%2F%20val%2Fweight%20ratio%0Abool%20cmp(Item%20a%2C%20Item%20b)%0A%7B%0A%20%20%20%20double%20r1%20%3D%20(double)a.value%20%2F%20a.weight%3B%0A%20%20%20%20double%20r2%20%3D%20(double)b.value%20%2F%20b.weight%3B%0A%20%20%20%20return%20r1%20%3E%20r2%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20bound%20of%20profit%20in%20subtree%20rooted%20with%20u.%0A%2F%2F%20This%20function%20mainly%20uses%20Greedy%20solution%20to%20find%0A%2F%2F%20an%20upper%20bound%20on%20maximum%20profit.%0Aint%20bound(Node%20u%2C%20int%20n%2C%20int%20W%2C%20Item%20arr%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20if%20weight%20overcomes%20the%20knapsack%20capacity%2C%20return%0A%20%20%20%20%2F%2F%200%20as%20expected%20bound%0A%20%20%20%20if%20(u.weight%20%3E%3D%20W)%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%0A%20%20%20%20%2F%2F%20initialize%20bound%20on%20profit%20by%20current%20profit%0A%20%20%20%20int%20profit_bound%20%3D%20u.profit%3B%0A%20%0A%20%20%20%20%2F%2F%20start%20including%20items%20from%20index%201%20more%20to%20current%0A%20%20%20%20%2F%2F%20item%20index%0A%20%20%20%20int%20j%20%3D%20u.level%20%2B%201%3B%0A%20%20%20%20int%20totweight%20%3D%20u.weight%3B%0A%20%0A%20%20%20%20%2F%2F%20checking%20index%20condition%20and%20knapsack%20capacity%0A%20%20%20%20%2F%2F%20condition%0A%20%20%20%20while%20((j%20%3C%20n)%20%26%26%20(totweight%20%2B%20arr%5Bj%5D.weight%20%3C%3D%20W))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20totweight%20%20%20%20%2B%3D%20arr%5Bj%5D.weight%3B%0A%20%20%20%20%20%20%20%20profit_bound%20%2B%3D%20arr%5Bj%5D.value%3B%0A%20%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20k%20is%20not%20n%2C%20include%20last%20item%20partially%20for%0A%20%20%20%20%2F%2F%20upper%20bound%20on%20profit%0A%20%20%20%20if%20(j%20%3C%20n)%0A%20%20%20%20%20%20%20%20profit_bound%20%2B%3D%20(W%20-%20totweight)%20*%20arr%5Bj%5D.value%20%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D.weight%3B%0A%20%0A%20%20%20%20return%20profit_bound%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20maximum%20profit%20we%20can%20get%20with%20capacity%20W%0Aint%20knapsack(int%20W%2C%20Item%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20sorting%20Item%20on%20basis%20of%20value%20per%20unit%0A%20%20%20%20%2F%2F%20weight.%0A%20%20%20%20sort(arr%2C%20arr%20%2B%20n%2C%20cmp)%3B%0A%20%0A%20%20%20%20%2F%2F%20make%20a%20queue%20for%20traversing%20the%20node%0A%20%20%20%20queue%3CNode%3E%20Q%3B%0A%20%20%20%20Node%20u%2C%20v%3B%0A%20%0A%20%20%20%20%2F%2F%20dummy%20node%20at%20starting%0A%20%20%20%20u.level%20%3D%20-1%3B%0A%20%20%20%20u.profit%20%3D%20u.weight%20%3D%200%3B%0A%20%20%20%20Q.push(u)%3B%0A%20%0A%20%20%20%20%2F%2F%20One%20by%20one%20extract%20an%20item%20from%20decision%20tree%0A%20%20%20%20%2F%2F%20compute%20profit%20of%20all%20children%20of%20extracted%20item%0A%20%20%20%20%2F%2F%20and%20keep%20saving%20maxProfit%0A%20%20%20%20int%20maxProfit%20%3D%200%3B%0A%20%20%20%20while%20(!Q.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Dequeue%20a%20node%0A%20%20%20%20%20%20%20%20u%20%3D%20Q.front()%3B%0A%20%20%20%20%20%20%20%20Q.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20it%20is%20starting%20node%2C%20assign%20level%200%0A%20%20%20%20%20%20%20%20if%20(u.level%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20v.level%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20there%20is%20nothing%20on%20next%20level%0A%20%20%20%20%20%20%20%20if%20(u.level%20%3D%3D%20n-1)%0A%20%20%20%20%20%20%20%20%20%20%20%20continue%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Else%20if%20not%20last%20node%2C%20then%20increment%20level%2C%0A%20%20%20%20%20%20%20%20%2F%2F%20and%20compute%20profit%20of%20children%20nodes.%0A%20%20%20%20%20%20%20%20v.level%20%3D%20u.level%20%2B%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Taking%20current%20level’s%20item%20add%20current%0A%20%20%20%20%20%20%20%20%2F%2F%20level’s%20weight%20and%20value%20to%20node%20u’s%0A%20%20%20%20%20%20%20%20%2F%2F%20weight%20and%20value%0A%20%20%20%20%20%20%20%20v.weight%20%3D%20u.weight%20%2B%20arr%5Bv.level%5D.weight%3B%0A%20%20%20%20%20%20%20%20v.profit%20%3D%20u.profit%20%2B%20arr%5Bv.level%5D.value%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20cumulated%20weight%20is%20less%20than%20W%20and%0A%20%20%20%20%20%20%20%20%2F%2F%20profit%20is%20greater%20than%20previous%20profit%2C%0A%20%20%20%20%20%20%20%20%2F%2F%20update%20maxprofit%0A%20%20%20%20%20%20%20%20if%20(v.weight%20%3C%3D%20W%20%26%26%20v.profit%20%3E%20maxProfit)%0A%20%20%20%20%20%20%20%20%20%20%20%20maxProfit%20%3D%20v.profit%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Get%20the%20upper%20bound%20on%20profit%20to%20decide%0A%20%20%20%20%20%20%20%20%2F%2F%20whether%20to%20add%20v%20to%20Q%20or%20not.%0A%20%20%20%20%20%20%20%20v.bound%20%3D%20bound(v%2C%20n%2C%20W%2C%20arr)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20bound%20value%20is%20greater%20than%20profit%2C%0A%20%20%20%20%20%20%20%20%2F%2F%20then%20only%20push%20into%20queue%20for%20further%0A%20%20%20%20%20%20%20%20%2F%2F%20consideration%0A%20%20%20%20%20%20%20%20if%20(v.bound%20%3E%20maxProfit)%0A%20%20%20%20%20%20%20%20%20%20%20%20Q.push(v)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Do%20the%20same%20thing%2C%20%20but%20Without%20taking%0A%20%20%20%20%20%20%20%20%2F%2F%20the%20item%20in%20knapsack%0A%20%20%20%20%20%20%20%20v.weight%20%3D%20u.weight%3B%0A%20%20%20%20%20%20%20%20v.profit%20%3D%20u.profit%3B%0A%20%20%20%20%20%20%20%20v.bound%20%3D%20bound(v%2C%20n%2C%20W%2C%20arr)%3B%0A%20%20%20%20%20%20%20%20if%20(v.bound%20%3E%20maxProfit)%0A%20%20%20%20%20%20%20%20%20%20%20%20Q.push(v)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20maxProfit%3B%0A%7D%0A%20%0A%2F%2F%20driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20W%20%3D%2010%3B%20%20%20%2F%2F%20Weight%20of%20knapsack%0A%20%20%20%20Item%20arr%5B%5D%20%3D%20%7B%7B2%2C%2040%7D%2C%20%7B3.14%2C%2050%7D%2C%20%7B1.98%2C%20100%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B5%2C%2095%7D%2C%20%7B3%2C%2030%7D%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%20%2F%20sizeof(arr%5B0%5D)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Maximum%20possible%20profit%20%3D%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20knapsack(W%2C%20arr%2C%20n)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]
Output :
Maximum possible profit = 235[ad type=”banner”]