#### 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.