0/K 背包。怎么解决？
0/K knapsack. How to solve?
我正在尝试学习动态规划。我遇到了：https://youtu.be/U4O3SwDamA4?t=1407
我知道 DP 的基础知识，尽管它们对我来说还不直观。现在，他谈到
- 0/1个背包
- 0/inf 背包
最后是0/k背包
当我尝试搜索 0/k 背包时，我得到的是优化解 (O(nS))，而不是直接从 0/1 中提取的解，其复杂度为 O(nKS)。欢迎任何有资源分享或掌握相同资源的人:)谢谢
我认为演示者简要提到的“天真”解决方案具有运行时复杂性 O(KS)，考虑到他定义的方式 K 是所有项目限制的总和。这个想法是通过制作每个项目类型的 ki 副本将其转换为 0/1 问题。
假设您有 k0 项类型 0，k1 类型 1 的项目，依此类推（因此这些是每种类型的项目数量限制）。 K是项目总数（所有ki的总和）。现在，如果您使用这个项目集合并开始考虑 每个 项目与所有其他项目不同，您就会遇到 0/1 问题！类型 0 的第一项现在是我们新问题中的项目 0，类型 0 的第二项是我们新问题中的项目 1，类型 0 的最后一项是项目 k0 - 1 在我们的新问题中 - 他们都有权重 w0 和价值 v0。类型 1 的第一项是我们新问题中的项 k0，依此类推。所以我们现在可以将其作为 0/1 背包问题来解决，但是它有 K 项而不是 n；因此，复杂度为 O(KS)。但是，如果您将 K 定义为所有 ki 的 平均值 ，或者如果每一项都有相同的极限K，那么复杂度确实是O(nKS).
我正在尝试学习动态规划。我遇到了：https://youtu.be/U4O3SwDamA4?t=1407 我知道 DP 的基础知识，尽管它们对我来说还不直观。现在，他谈到
- 0/1个背包
- 0/inf 背包
最后是0/k背包
当我尝试搜索 0/k 背包时，我得到的是优化解 (O(nS))，而不是直接从 0/1 中提取的解，其复杂度为 O(nKS)。欢迎任何有资源分享或掌握相同资源的人:)谢谢
我认为演示者简要提到的“天真”解决方案具有运行时复杂性 O(KS)，考虑到他定义的方式 K 是所有项目限制的总和。这个想法是通过制作每个项目类型的 ki 副本将其转换为 0/1 问题。
假设您有 k0 项类型 0，k1 类型 1 的项目，依此类推（因此这些是每种类型的项目数量限制）。 K是项目总数（所有ki的总和）。现在，如果您使用这个项目集合并开始考虑 每个 项目与所有其他项目不同，您就会遇到 0/1 问题！类型 0 的第一项现在是我们新问题中的项目 0，类型 0 的第二项是我们新问题中的项目 1，类型 0 的最后一项是项目 k0 - 1 在我们的新问题中 - 他们都有权重 w0 和价值 v0。类型 1 的第一项是我们新问题中的项 k0，依此类推。所以我们现在可以将其作为 0/1 背包问题来解决，但是它有 K 项而不是 n；因此，复杂度为 O(KS)。但是，如果您将 K 定义为所有 ki 的 平均值 ，或者如果每一项都有相同的极限K，那么复杂度确实是O(nKS).