# Input:
# - vector w with weights of n items
# - vector v with value of n items
# - W maximal amount of weight I can carry
#
# Output:
# - vector n with amount of item taken (between 0 and 1)

KnapSack(W,w,v) {
  n := [0,...,0]
  r = w/v pointwise   // linear time
  p,r := sort_and_remember(r)  // O(n log n)
  i = 1
  while W > 0 and i <= length(r) {
    if W >= w[p[i]] then
      W := W - w[p[i]]
      n[p[i]] = 1
      i := i + 1
    else
      f := W / w[p[i]]
      W := 0
      n[p[i]] := f
  }
  return n
}

# complexity:
# - O(n) for pointwise division
# - O(n log n) for sorting
# - O(n) for the while loop
    (each item is considered at most once)
# overall: O(n log n)
w/v poitwise {
  for i = 1 to length(w)
   r[i] := w[i] / v[i]
  return r
}

# input:
# - a list of numbers to sort in decreasing order
#
# output:
# - the list r of sorted elements of the input
# - a second list p s.t. p[i] = j iff element i of r
#   was in position j before the sorting
#
# example:  p,r := sort_and_remember([3,1,14,10,8])
# output:   r = [1,3,8,10,14]
#           p = [2,1,5,4,3]