高级
复杂动态规划算法优化
解决一个复杂的资源分配问题，并要求对算法的时间复杂度进行优化。
📝 Treść promptu
给定一个背包容量为 W，以及 N 个物品，每个物品有重量 w[i]、价值 v[i] 和一个特殊的属性 k[i]（表示该物品属于某个特定类别）。要求：每个类别的物品最多只能选择一个。请编写一个 Python 函数 solve_knapsack_with_categories(W, N, w, v, k) 来计算能够装入背包的物品的最大总价值。除了提供代码外，请详细分析该问题的时间复杂度和空间复杂度，并讨论是否可以使用状态压缩或其他优化技术来降低复杂度。请提供标准解法、空间优化解法以及对比分析。