Knapsack Problem

computation

Definition

Knapsack Problem

Given a multiset of integer-pairs of form , where is the weight and is the price of an item, and integers (maximum weight) and (minimum price). The knapsack problem asks whether there exists a subset such that:

Input:

Knapsack Problem

The Knapsack problem is a problem that asks for filling a fixed-size knapsack with items that have a size and a value such that the total value of the knapsack is maximised. Greedy algorithms on the value of the elements won’t work here.

The Knapsack problem is an optimisation problem is about maximising

whereby

where , is the value and of item , is the maximum weight capacity of the knapsack, and

Approaches

Naive Enumeration

Time Complexity: (can’t really be improved generally speaking)

Branch and Bound

Branch and bound is used here to omit certain subtrees in search space that are not expected to increase the current optimum under the assumption of monotonicity.

If , then we cannot find any better solution that the current best solution.

Example: Given items and a knapsack with capacity .

Item	1	2	3	4
Weight	32	16	21	50
Value	80	20	63	100
Coefficient	2.5	1.25	3	2

Order the items according to their coefficients:

1. Item with
2. Item with
3. Item with
4. Item with

Enumerate :

1. Select given that .
   1. (total weight for current enumeration)
   2. (rest capacity for current enumeration)
2. Select given that
3. Can’t selected given that :
   1. (remains the same)
   2. (remains the same)
   3. (remains the same)
4. Select given that
   1. (remains the same)
   2. (remains the same)
   4. (remains the same)
5. Effects:
   • (best solution so far)
   • (best solution so far)

Observation

As soon as the first item is found that does not fit inside the knapsack in the current enumeration, i.e. , the current capacity , the rest capacity , and the upper bound are fixed. After that, only the lower bound could be adjusted, where possible.

Enumerate: What if is chosen?

• This is equivalent to the enumeration above. Thus:
• Effects:

Enumerate: What if and are chosen?

• This is equivalent to the enumeration above. Thus:
• Effects:

Enumerate: What if , , are chosen?

• This is the first occurrence that differs from the enumerations above since were not chosen since it didn’t fit into the Knapsack’s capacity.
• Therefore, this state (and its subsequent subspace) can be ignored.

Enumerate: What if , are chosen, but is not chosen?

• In the first enumeration, we tried to put into the Knapsack’s upper boundary. Now, we don’t put into the knapsack at all. Thus:
• Effects:
  • (unchanged)
  • (updated)
  • (unchanged)
  • (unchanged)
• Bound:
  • Given that , we already found the best solution in the current sub-state space. Further solutions in the current sub-state space don’t need to be explored.

Enumerate: What if is chosen, but is not chosen?

1. Select given that .
   1. (total weight for current enumeration)
   2. (rest capacity for current enumeration)
2. Next item would be , however, we decided to omit it.
3. Select given that
4. Select given that
   5. We do not add any fraction to given that there are no more elements that could be added.
5. Effects:
   3. (updated)
   4. (unchanged)
6. Bound:
   1. Again, given that , we can bound here. There’s no better solution in the current sub-state space.

Enumerate: What if is not chosen?

1. First item would be , however, we decided to omit it.
2. Select given that :
3. Select given that
4. Select given that
   5. Again, no fraction is added to given that no further items are available to be selected.
5. Effects:
   3. (updated)
   4. (updated)
6. Bound:
   1. Again, given that , the best possible solution in the current sub-state space is found. No further exploration needed.

The entire search space is now explored. The most optimal solution is:

• ( is omitted)

Dynamic Programming

The knapsack problem is a classic example for using dynamic programming for a problem. Given items, where each item has a size and a value, you try to solve all sub-problems for . During solving this problem, a table is built:

	0	1	2	…
0	0	0	0	…	0
1				…
2				…
…	…	…	…	…	…
				…

After the DP table is built, the algorithm just chooses based on the table dp[n][max_size].

TL;DR: Dynamic Programming Approach

The dynamic programming approach solves the problem for all and , builds up a table and picks the solution for the desired problem.

Solutions of smaller problems can be used for the next bigger problem, until the desired problem is picked.

Python:

def knapsack(max_size: int, items: list[tuple[int, int]]) -> int:
	n: int = len(items)
	dp: list[list[int]] = [
		[0] * (max_size + 1)
		for _ in range(n + 1)
	]
	for i in range(1, n + 1):
		item_size, item_value = items[i - 1]
			for w in range(max_size + 1):
				if item_size <= w:
					dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - item_size] + item_value)
				else:
					dp[i][w] = dp[i - 1][w]
	return dp[n][max_size]