concept knapsack in category algorithms

This is an excerpt from Manning's book Grokking Algorithms: An illustrated guide for programmers and other curious people. Login to get full access to this book.

Suppose you’re a greedy thief. You’re in a store with a knapsack, and there are all these items you can steal. But you can only take what you can fit in your knapsack. The knapsack can hold 35 pounds.

Let’s revisit the knapsack problem from chapter 8. You’re a thief with a knapsack that can carry 4 lb of goods.

You have three items that you can put into the knapsack.

This is an excerpt from Manning's book Grokking Artificial Intelligence Algorithms. Login to get full access to this book.

Table 4.1 Knapsack weight capacity: 9 kg (view table figure)

Item ID	Item name	Weight (kg)	Value ($)
1	Pearls	3	4
2	Gold	7	7
3	Crown	4	5
4	Coin	1	1
5	Axe	5	4
6	Sword	4	3
7	Ring	2	5
8	Cup	3	1

Figure 4.12 Binary-encoding the Knapsack Problem

To make things interesting, the refinery requires a steady rate of extraction, given the extraction time and the value of the item. It’s assumed that the value of the refined material is more or less the same as the value of the item. The problem becomes an ordering problem. In what order should the items be processed to maintain a constant rate of value? Table 5.2 describes the items with their respective extraction times.