Imagine the following situations:

- A truck loading cargo
- A shopper on a budget
- A thief stealing from a house using a large bag
- A child eating candy very quickly

All of these are examples of ***The Knapsack Problem***, where there are more things that you ***want*** to take with you than you ***can*** take with you.

The Problem
===

Given a container with a certain capacity and an assortment of discrete items with various sizes and values (and an infinite supply of each item), determine the combination of items that fits within the container and maximizes the value of the collection.

However, **DO NOT** attempt to solve the problem **EXACTLY!** (we will do that in Part 2)


The Simplification
===

Because the optimal collection of items is **MUCH** more difficult to determine than a nearly-optimal collection, this kata will only focus on one specific nearly-optimal solution: the greedy solution. The greedy solution is that which always adds an item to the collection if it has the highest value-to-size ratio.

For example, if a "greedy thief" with a 10-Liter knapsack sees two types of items

- a 6-Liter item worth $9 (1.5 $/L)

- a 5-Liter item worth $5 (1.0 $/L)

the thief will take 1 of the 6-Liter items instead of 2 of the 5-Liter items. Although this means the thief will only profit $9 instead of $10, the decision algorithm is much simpler. Maybe the thief is bad at math.

Now, go be bad at math!


The Kata
===

Write the function `knapsack` that takes two parameters, `capacity` and `items`, and returns a list of quantities.

`capacity` will be a positive number

`items` will be an array of arrays of positive numbers that gives the items' sizes and values in the form [[size 1, value 1], [size 2, value 2], ...]

`knapsack` will return an array of integers that specifies the quantity of each item to take according to the greedy solution (the order of the quantities must match the order of `items`)

Difficulty: introductory

Starter code:

def knapsack(capacity, items):
	

Solutions:
def knapsack(capacity, items):
    ratios = [float(item[1]) / item[0] for item in items]
    collection = [0] * len(items)
    space = capacity
    while any(ratios):
        best_index = ratios.index(max(ratios))
        if items[best_index][0] <= space:
            collection[best_index] += 1
            space -= items[best_index][0]
        else:
            ratios[best_index] = 0
    return collection

def knapsack(c, items):
    qtys = [0 for i in items]
    weights = sorted(items, reverse=True, key=lambda (size, value): float(value)/size)
    for (size, value) in weights:
        qty = c // size
        qtys[items.index((size, value))] = qty
        c -= qty * size
    return qtys

def knapsack(capacity, items):
    r = [0] * len(items)
    for i, item in sorted(enumerate(items), key=lambda x: x[1][1] / float(x[1][0]), reverse=True):
        while capacity >= item[0]:
            capacity -= item[0]
            r[i] += 1
    return r

def knapsack(capacity, items):
  sortItems = sorted(items, key=lambda tup: (tup[1] / float(tup[0])))[::-1]
  sortCount = [(i[0], i[1], 0) for i in sortItems]
  rCap = capacity
  for i in range(len(sortCount)) :
    while rCap >= sortCount[i][0] :
      sortCount[i] = (sortCount[i][0], sortCount[i][1], sortCount[i][2] + 1)
      rCap -= sortCount[i][0]
  counts = [sortCount[sortItems.index(i)][2] for i in items]
  return counts

def knapsack(capacity, items):
    quantities = [0] * len(items)
    for idx, (size, value) in sorted(enumerate(items),
                key=lambda it: it[1][1] / it[1][0], reverse=True):
        quantities[idx], capacity = divmod(capacity, size)
    return quantities

def knapsack(capacity, items):
    arr = sorted(enumerate(items), key = lambda x: x[1][1]/x[1][0], reverse = True)
    sack = [0]*len(items)
    
    for j, (w, v) in arr:
        if w <= capacity:
            sack[j], capacity = divmod(capacity, w)
    
    return sack

def knapsack(capacity, items):
    ratios = [float(item[1]) / item[0] for item in items]
    collection = [0] * len(items)
    space = capacity
    while True:
        best_index = ratios.index(max(ratios))
        if items[best_index][0] <= space:
            collection[best_index] += 1
            space -= items[best_index][0]
        else:
            ratios[best_index] = 0
        if all(ratio == 0 for ratio in ratios):
            return collection

def knapsack(capacity, items):
    liste = sorted([ x+(i,) for i,x in enumerate(items)], key= lambda x: x[1]/x[0], reverse = True)
    result = [0]*len(items)
    for s,v,i in liste :
        if capacity >= s :
            result[i] = int(capacity/s)
            capacity -= result[i]*s
    return result

def knapsack(capacity, items):
    res = [0] * len(items)
    vsi = sorted(((v / s, s, c) for c, (s, v) in enumerate(items)), reverse=True)
    for _, s, c in vsi:
        res[c], capacity = divmod(capacity, s)
    return res

def knapsack(capacity, items):
    L = sorted((-y/x, x, i) for i,(x,y) in enumerate(items))
    res = [0]*len(L)
    for _, x, i in L:
        res[i], capacity = divmod(capacity, x)
    return res