Optimizing the knapsack problem.

 I suppose that you know the knapsack problem with 2 parameters. So here is how we are going to optimize it. You know that we are keeping an array C where C[i] shows the best value we have got by using i weight. Every time we loop over this array and if we find an element which is not 0( has been used previously) we check if by adding the new weight and a new value we can get a better value of not. Every time we loop we check many elements which are 0 (which we haven't used yet), it would be much better if we just looped over the elements which have a value greater than 0 to save time right?, Here is how we will do it, we will need to keep another array suppose D where D[i] shows the next index which is not 0. Initially D[1]=1 and size of D is 1 because there is only one element which we used from the beginning. Then instead of looping over array C we will loop over array D and check, if by using a new weight we got into a cell which is 0 we need to add that to our array D so that next time we loop over that spot as well. Now about adding element to array D, If in the task we have a limited numbed of elements (meaning that we cannot choose infinite number of elements, we can choose only one) then in the slow approach we were looping over array C from the end so that we won't count the same number more than once, in here we need to keep our array D sorted in increasing order so that we will not lose the right answer, there are 2 ways of doing that either sorting the entire array D or using binary search for finding the appropriate spot of the new element and insert it in the middle of our array D.