定义
$I={1，2,…,N}$是商品的集合。
当每个商品的重量为 $i in I$
的权重为 $w_i$ 价值为 $v_i$
商品重量的总上限为 $W$ 时
，将出现以下内容称为背包问题。
$$
max ∑{i in I}v_iw_i s.t. ∑{i}v_iw_ile W
xinmathbb{N}（forall in I）
$$
，其中$x_i$表示要放入背包中的物品数。
解决方案
问题是，如果你搜索整个数字，你会尝试两个选项，“选择或不选择物品”，只有几分钟的货物，计算金额是$O（2^{| I|}) 成为$ 但是，通过有效的贪婪方法的解法是已知的，在这里显示了解决方案。 这个问题的渐化公式是
$$
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}
$$
成为。 此处，$V （i， w） $ 的值表示重量之和为 $w$ 或更少时，可以使用下标为 $i$ 或更低的商品实现的总价值的最大值。 这个公式是
- 当“一个不能选择一件物品”或“最大重量为 ${显示样式 0}{显示样式 0}$”时，由于没有要包装的物品，因此所选项目的总价值为 ${显示样式 0}{显示样式 0}$
- 如果项目 ${显示样式 i}$ 的权重超过 ${显示样式 w}$，则无法添加项目 ${显示样式 i}$，因此总值是项目下标上限为前一个值的最大值。
- 如果项目 ${显示样式 i}$ 的权重不超过 ${显示样式 w}$，则不添加项目 ${显示样式 i}$ 的值最大值应为不小的值。
它表示。 伪代码如下所示。 总价值的最大值为 V（| I|，W） 获得。 此外，还需要添加代码来枚举所选项目。