Defined
$I={1,2,…,N}$ is the set of goods.
When
the weight of each item $i in I$ is $w_i$ value and the upper limit of the total weight of $ v_i$
item is $W$, the following is called the knapsack problem.
$$
max ∑{i in I}v_iw_i s.t. ∑{i in I}v_iw_ile Wxin mathbb{N}(forall
in I)
$$ where $x_i$
represents the number of items to be placed in the knapsack.
solution
The problem is that if you perform a total search, you will try two options of "select or not select items" for the number of items, and the computational complexity is $O(2^{| I|}) Become $. However, an efficient solution method by the greedy method is known, and the solution method is shown here. The recurrence formula in this problem is
$$
V(i,w)
=begin{cases}
{0quad if,i= 0,or,w = 0}
{V(i-1,w)quad if,w_i>w}
{max(V(i-1),V(i-1,w-w_i)+v_i)quad otherwise}
end{cases}
$$
Become. where $V(i, w)$ represents the maximum value of the total value that can be realized using goods with a subscript of $i$ or less if the sum of their weights is less than or equal to $w$. This formula is
- If "no items can be selected" or "the maximum weight is ${displaystyle 0}{displaystyle 0}$", the sum of the values of the selected items is ${displaystyle 0}{displaystyle 0}$ because there are no items to pack.
- If the weight of the item ${displaystyle i}$ exceeds ${displaystyle w}$, the item ${displaystyle i}$ cannot be added, so the total value is the maximum value of the item up to one previous subscript limit.
- If the weight of item ${displaystyle i}$ does not exceed ${displaystyle w}$, the item ${displaystyle i}$ should be the least less, either the maximum value of adding the item ${displaystyle i}$ or the maximum value of the addition of the item.
It shows that. The pseudocode is as follows. The maximum value of the sum is V(| I|, W). In addition, enumerating the selected items requires the addition of code.