And we can start with the same array of amounts and

the same total value filled with zeroes.

But then we make a for loop for i going from 1 to n.

And on each iteration i will be the best unit which is still left.

So on the start of the iteration we check whether we still have some capacity

in the knapsack.

If it is already filled we just return the answer.

Otherwise we know that i is the best item

because we didn't consider it previously and it is the item with the maximum

value per unit out of those which we didn't consider before.

So we determine the amount of this item with the same formula and

we update the weights, the amounts, the capacity, and

the total value in the same way as we did in the previous pseudocode.

The only change is that we change the order in which we consider the items.

And this allows us to make each iteration in constant time instead of linear time.

So, this new algorithm now works in linear time, because it has at most n iterations,

and each iteration works at most in constant time.

So, if we apply first some sorting algorithm

to sort items by decreasing value of vi over wi.

And then apply this new knapsack procedure.

Total run time will be n log n, because sorting will work in n log n.

And the knapsack itself will work in linear time.