I am writing a program in java that solves the knapsack problem for an arbitary knapsack capacity amd series of weights. Assume the weights are stored in an array.The arguments to the recursive knapsack() function are the target weight and the array index where the remaining items start.. USE THE CONSOLE FOR INPUT and output

the target FIRST followed by the weights(there will be no repeated values). Permit the user to enter all the numbers on one line: 20 11 8 7 6 5 In this case the output would be: 8 7 5 Be sure and show all possible solutions! This is important!!!!. You may assume that the largest capacity (as well as any individual weight) is 100 and the largest number of weights is 25. You may also assume that the weights are sorted from largest to smallest. The basic idea is to send a capacity and an array of weights to a recursive method and to either insert the weight or not. In either case call the method again with a reduced capacity and a shorter array OR with the same capacity and a shorter array. There should be a base case(s) for easy capacity and/or easy array. IF you do it this way, you would probably return another array which would be the potential solution array which of course would only be printed it it is truly a solution. There are multiple ways to attack the problem but recursion MUST be used! A design issue is whether to send two arrays or whether you want to send one array and return another. It is your choice!