多重背包如何解决不同物品数量限制的长尾词问题？

本文共计2542个文字，预计阅读时间需要11分钟。

多重背包问题前准备：

在阅读本文之前，需要掌握以下内容：

1. 基础dp背包算法

2.单调队列

3.多重背包问题是什么

4.多重背包问题定义：

给定 + 种物品，每种物品有若干件，每件物品有价值和重量，求按重量限制装物品的最大价值。

具体内容如下：

多重背包问题定义：给定 + 种物品，每种物品有若干件，每件物品有价值和重量，求按重量限制装物品的最大价值。

多重背包笔记 前置芝士

在看本文之前，需要掌握：

基础dp背包算法;
单调队列

多重背包问题是什么

多重背包是指这样一类问题：给定\(n\)种物体，每种物体具有三个属性\(v\)，\(w\)，\(c\)，分别代表其体积，价值和数量。要求在其中选出一些，满足第\(i\)种物品最多选择\(c_i\)个，体积总和\(sum_v \leq m\)，使得价值总和\(sum_w\)最大。
输入数据一般形如：

第1行输入两个数\(n\)和\(m\)
第\(2\)~\((n+1)\)行每行3个数\(v\)，\(w\)，\(c\)表示一个物体。

题目链接

朴素解法
常规解法：二进制拆分
最优解：单调队列优化

朴素解法

动态规划的状态\(f_{i,j}\)表示前\(i\)种物体刚好放满容量为\(j\)的背包中获得的最大价值。显然可以枚举i，j，对于\(i\)的每次转移都考虑选取该类物品中的多少个。其时间复杂度为\(O(m*sum_c)\)，基本不可接受。