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`)

Source: codewars | Difficulty: EASY
Tags: Sorting

Mathematics

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(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