Competitive Programming

0 1 Knapsack Problem – Dynamic Programming Solution: Problem Description: Given weights and values of n items, put these items in a knapsack of capacity M to get the maximum total value in the knapsack. Note that, you can select items, the sum of whose weight is less than or equal to the capacity of knapsack, W. Problem Solution: The problem is to find a subset of items such that –  the sum of weight of all the items in the subset should be less than or equal to knapsack capacity  out of all subsets that satisfy criteria 1 above, the desired subset is the one in which the sum values of its items is maximum. Expected Input and Output: Case-1: number of items, n=4 weight of items, w[]=2 3 4 5 value of items,  v[]=3 4 5 6 capacity of knapsack, M=5 maximum attainable value of items=7   by collecting first and second item in the knapsack. Case-2:   n=3 w[]=3 2 1 v[]=5 3 4 M=5 maximum attainable value of items=9  by collecting first and last item in the knap...