问题描述

有N件物品和一个容量是V的背包。每件物品只能使用一次

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

背包问题类型

1、0/1背包问题:每个元素最多选取一次
2、完全背包问题:每个元素可以重复选择
3、组合背包问题:背包中的物品要考虑顺序
4、分组背包问题:不止一个背包,需要遍历每个背包

背包问题分类

1、最值问题:要求最大值/最小值
2、存在问题:是否存在…………,满足…………
3、组合问题:求所有满足……的排列组合