Knapsack problem
Mathematically the problem can be formulated as follows: there are loads. For each i-th load is defined weight and value . Given the capacity of W. to Select a subset of goods, so that their total weight does not exceed W, and the total value would be the maximum.
o1, o2,...,on is loads.
oi=(wi, pi), i=1,2,3,...,n.
wi is weight of oi, pi is value (price) of oi.
On={o1, o2,...,on}.
(On, ρ1), ρ1(oi)=wi, i=1,2,3,...,n.
(On, ρ2), ρ2(oi)=pi, i=1,2,3,...,n.
∑(On)={A: A⊂On}.
ρ1(A)=∑oi∈A ρ1(oi)=∑oi∈A wi.
ρ2(A)=∑oi∈A ρ2(oi)=∑oi∈A pi.
∑w(On)={A: A⊂On, ρ1(A)≤W}.
(∑w(On), ρ2).
max{ρ2(A): A∈∑w(On)}=pmax.
wKn={A: A∈∑w(On), ρ2(A)=pmax}.
Emzari Papava
| 
