KNAPSACK PROBLEM

Introduction

Given two arrays namely weights and price, and the capacity of the knapsack(container) M, determine the item(s) that are to be included in the knapsack so that the total weight is less than or equal to a given limit and the total price is as large as possible(max. profit).

Simply we need to find the most valuable subset of the items that fit into the knapsack and here, will find the total value i.e max profit.

Working Procedure

  • Let weights[n], price[n] be two arrays and M be the max capacity of the knapsack. Variable i corresponds to items,(0 to n) and j corresponds to capacity(0 to M).
  • Let V[n+1][m+1] be the array to store profit amount(in program, will use recursion) and the max profit will be stored in V[n][m].
  • If i==0 or j==0 then return 0. Because if either the no. of items selected or capacity is 0 then obviously the max profit is 0.
  • If weights[ i ] > j then return V[ i-1 ][ j ]. That is to say if the weight of the item is greater than capacity then we can't include it, so return the previous item's profit corresponding to same capacity.
  • Else if weights[ i ] <= j then return max(V[ i-1 ][ j ] , price[ i ] + V[ i-1 ][ j-weights[ i ] ). That means if the weight is lesser than or equal to the capacity then if we have two options to find max profit for this capacity:
    1. Previous item's profit corresponding to same capacity.
    2. Current item + other items excluding current item.
    Return the maximum of these two.

Time Complexity: O(n*M)

Similar posts: Dynamic Programming | Warshall's Algorithm | Floyd's Algorithm

Code file

Please open this in your pc or with a compatible app in your mobile.

C++ Implementation for KNAPSACK PROBLEM

That's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!

Copyright © NStF Blogs 2021