多重背包问题属于动态规划范畴

多重背包

多重背包问题源于0-1背包问题的拓展，在着手解决多重背包问题之前，有必要先对0-1背包问题进行初步了解。

0-1背包问题解析

问题描述：假设有n类物品与一个背包。其中，物品i的重量为w，对应的价值为v，而背包的最大承载能力为C。现需确定如何选取物品放入背包，以实现所装物品总价值的最大化？

在进行物品选取时，对于每类物品i而言，仅存在两种决策方式：将其放入背包或不放入背包。不允许对同一物品进行多次装入，也不允许仅装入该物品的一部分。因此，此类问题被定义为0-1背包问题。

多重背包

①存在一个具有多维容量限制的背包，其在n个不同维度上的容量参数为 [c1,c2…cn] 。这些维度可以涵盖诸如承载重量、占据体积等多样化属性。

②共有m件待选物品，其中每件物品i在n个维度上所占用的资源量为 [w1,w2…wn] ，并且每件物品i对应的价值量为 v[i] 。

③目标是从这m件物品中选择合适的组合装入背包，在确保各维度上总资源消耗不超过对应容量限制的前提下，实现背包内物品总价值的最大化。

解决背包问题的常用算法有：

①贪