A little bit about packing a backpack

Many people know the so-called task of packing a backpack.
Let me remind you briefly: from a pile of objects you need to choose such that the backpack is crammed to the eyeballs and it can still be fired.
Speaking 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 a does not exceed the predetermined S, and the sum of the numbers b is maximum. Σa (n) ≤ S, Σb (n) = max.

Source Set:

											Σ
a	3	14	25	26	32	2	28	23	1	9	163
b	eleven	12	5	thirty	31	25	19	27	32	33	225

The last column shows the total weight Σa of all items and their total cost Σb. The set S (carrying capacity) must not exceed Σa, otherwise the solution is trivial - we can take everything. Given these limitations, using the total cost Σb, we can evaluate how much the total cost of the resulting solution 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.

Value set d:

											Σ
a	3	14	25	26	32	2	28	23	1	9	163
b	eleven	12	5	thirty	31	25	19	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	1	2	3	9	23	26	32	14	28	25	163
b	32	25	eleven	33	27	thirty	31	12	19	5	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 at S = 60.

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	eleven	33	27	thirty	31	12	19	5	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 left after laying the first five objects turned out to be the size: 60-38 = 22. If you look at the set to the end, there is another object that is placed in this hole.

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	eleven	33	27	thirty	31	12	19	5	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 an optimal solution.

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

											Σ
a	1	2	3	9	23	26	32	14	28	25	163
b	32	25	eleven	33	27	thirty	31	12	19	5	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 an optimal solution.

Consider the limiting case. We have two items that are individually placed in a backpack, but not together. A natural solution would be to take a more expensive item, despite its greater weight. Obviously, the price of a stacked item has a higher priority than weight.
A small revaluation of the value of d allows us to shift the priority in the direction 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	1	2	9	3	26	23	32	14	28	25	163
b	32	25	33	eleven	thirty	27	31	12	19	5	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	1	2	9	3	26	23	32	14	28	25	163
b	32	25	33	eleven	thirty	27	31	12	19	5	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 laying the backpack is solved in linear time and is not complete NP.