编程学习分享 作者: xhm 时间: 2025-09-02 分类: 默认分类 多重背包问题 1.问题描述：每种物品可以用$l_i$次，求解在总体积不超过m的情况下最大收益。 2.动态规划思路：将每种物品拆成多个单位物品，每个单位物品只能用一次。 3.状态转移方程：fi j = max(fi-1 j， fi-1 j - vi + wi)。 4.复杂度优化：通过将物品拆分成O(log n)个单位物品，将复杂度优化到$n^2*log(n)$。 标签: none
