Given weights and values of n gift items. We have a box of capacity W. Find a solution such that the total value of gifts in the box is maximum.

In this Problem, we have two integer arrays value[0,1,2,…,n-1] and weight[0,1,2,3…,n-1],it represents the values and weights associated with n items resp. Given an integer W which represents the total capacity of the box. Write a Program to find the maximum value V which is the sum of the subset of values (value[]) such that the sum of the weight of this subset is smaller than or equal to W.

We either have to pick the complete gift item or don’t pick it.

Also known as 0-1 Knapsack Problem because we cannot split the item mentioned. Either we don’t pick the item (i.e 0) or pick the complete item (i.e 1).

Source: www.geeksforgeeks.org

Find Solution here