A little bit about packing backpack

Many people know the so-called task of packing a backpack.
In short, let me remind you: from a pile of items you need to choose such that the backpack was crammed to the eyeballs and could still be dragged away.
More formally, it is necessary from this set A of pairs of numbers a (i) b (i), to choose such that the sum of the numbers does not exceed the predetermined S, and the sum of the numbers b is maximum. Σa (n) ≤ S, Σb (n) = max.

Initial set:

											Σ
a	3	14	25	26	32	2	28	23	one	9	163
b	eleven	12	five	thirty	31	25	nineteen	27	32	33	225

The last column shows the total weight Σa of all items and their total value Σb. Asked S (load capacity) should not exceed Σa, otherwise the solution is trivial - we can carry everything. Given these limitations, using the total cost of Σb, we can estimate how much the total cost of the solution obtained differs from the absolute maximum.
')
There are several ways to solve this problem, they are described in Wikipedia.
We are interested in the "greedy" algorithm.
It consists in calculating for each pair the value d = a / b, by which the pairs are sorted and then selected.

Set indicating the value of d:

											Σ
a	3	14	25	26	32	2	28	23	one	9	163
b	eleven	12	five	thirty	31	25	nineteen	27	32	33	225
d	3.67	0.86	0.2	1.15	0.97	12.5	0.68	1.17	32.0	3.67

Sorted by d set

											Σ
a	one	2	3	9	23	26	32	14	28	25	163
b	32	25	eleven	33	27	thirty	31	12	nineteen	five	225
d	32.0	12.5	3.67	3.67	1.17	1.15	0.97	0.86	0.68	0.20

Let's try to find a solution with S = 60.

											Σ
a	one	2	3	9	23	26	32	14	28	25	163
b	32	25	eleven	33	27	thirty	31	12	nineteen	five	225
d	32.0	12.5	3.67	3.67	1.17	1.15	0.97	0.86	0.68	0.20

The first five items will give us Σa = 38, Σb = 128. The next item does not fit. With it, Σa = 64.
The hole remaining after laying the first five items turned out to be the size: 60-38 = 22. If you view the set to the end, there is another item that fits into this hole.

											Σ
a	one	2	3	9	23	26	32	14	28	25	163
b	32	25	eleven	33	27	thirty	31	12	nineteen	five	225
d	32.0	12.5	3.67	3.67	1.17	1.15	0.97	0.86	0.68	0.20

Total: Σa = 52, Σb = 140.

Unfortunately, this is not the optimal solution.

If we replace item 23-27 with 26-30,

											Σ
a	one	2	3	9	23	26	32	14	28	25	163
b	32	25	eleven	33	27	thirty	31	12	nineteen	five	225
d	32.0	12.5	3.67	3.67	1.17	1.15	0.97	0.86	0.68	0.20

then Σa = 55, Σb = 143, which is already the optimal solution.

Consider the limiting case. We have two items that are placed one by one in a backpack, but not together. The natural solution would be to take a more expensive item, despite its greater weight. Obviously, the price of the item being laid has a higher priority than weight.
A small revaluation of the value of d allows to shift the priority to the side we need.

Instead of the simple relation d = b / a, take d = b ² / a and still sort by d.

Sorted by d = b ² / a set

											Σ
a	one	2	9	3	26	23	32	14	28	25	163
b	32	25	33	eleven	thirty	27	31	12	nineteen	five	225
d	1024	312.5	121	40.33	34.6	31.7	30.0	10.3	12.9	1.0

For the same S = 60

											Σ
a	one	2	9	3	26	23	32	14	28	25	163
b	32	25	33	eleven	thirty	27	31	12	nineteen	five	225
d	1024	312.5	121	40.33	34.6	31.7	30.0	10.3	12.9	1.0

Σa = 55, Σb = 143. We immediately come to the optimal solution.

Thus, the task of packing a backpack is solved in linear time and is not NP complete.