Given n items of weight wi and value vi, find the items that should be taken such that the weight is less than the maximum weight W and the corresponding total value is maximum. This problem exhibits both overlapping subproblems and optimal substructure and is therefore a good candidate for dynamic programming.
Time complexity is O(n*W), where n is the total number of items and W is the maximum weight.
Complete Tutorial with Examples :
Rough notes about the Algorithm - as implemented in the code above: Firstly, input the total number of items, the weight and value of each item. Then input the maximum weight (maxWeight). Lastly calculate the maximum value that can be attained using Knapsack function. Knapsack function – This function takes total number of items (items), weight of all the items (weight), value of all the items (value) and the maximum weight (maxWeight) as arguments. It returns the maximum value that can be attained. Declare dp[items+1][maxWeight+1]. Where, dp[i][w] represents maximum value that can be attained if the maximum weight is w and items are chosen from 1...i. dp[w] = 0 for all w because we have chosen 0 items. And, dp[i] = 0 for all w because maximum weight we can take is 0. Recurrence:
for i=1 to items for w=0 to maxWeight dp[i][w] = dp[i-1][w], if we do not tale item i. if w-weight[i] >=0, suppose we take this item then, dp[i][w] = max(dp[i][w] , dp[i-1][w-weight[i]]+value[i]). Where, max is a function that returns the maximum of the two arguments it takes.
Related Tutorials (common examples of Dynamic Programming):
Some Important Data Structures and Algorithms, at a glance:
Basic Data Structures and Algorithms
Sorting- at a glance