装有各种物品的背包
knapsack with variety of items
假设一个普通的背包问题：你有一个重量限制，C，Value和Weight(V, W)的物品数量。您想要最大化 V 而 W 在 C 之下。本题每项只能有一个。
但是这个问题还有一个转折点。你想要各种各样的物品。假设问题表明您想要至少 5 件（或任意数量）不同的物品。如果解决方案中的不同项目少于 5 个，则答案无效。有解决此问题的方法吗？
这只是另一种形式的约束，所以让我们看看权重（最多 C 权重）和多样性（至少 5 个不同的项目）有何不同：
- 重量从有效开始（空袋低于 C），而多样性从无效开始（空袋不包含 5 个不同的项目）。
首先要注意的是，对于附加约束，您需要一个无效/不可解的概念，因为如果没有 5 个不同的项目满足权重约束，则没有解决方案。
一旦你定义了一种方法来 return 一些 invalid 结果，它真的很接近标准背包问题。在递归中，只需传递剩余的允许权重和当前多样性。在recursion anchor的情况下，检查Diversity，如果Diversity不满足要求，则return invalid，否则return结果和普通背包问题一样。检查 invalid 的递归结果并相应地处理它。
假设一个普通的背包问题：你有一个重量限制，C，Value和Weight(V, W)的物品数量。您想要最大化 V 而 W 在 C 之下。本题每项只能有一个。
但是这个问题还有一个转折点。你想要各种各样的物品。假设问题表明您想要至少 5 件（或任意数量）不同的物品。如果解决方案中的不同项目少于 5 个，则答案无效。有解决此问题的方法吗？
这只是另一种形式的约束，所以让我们看看权重（最多 C 权重）和多样性（至少 5 个不同的项目）有何不同：
- 重量从有效开始（空袋低于 C），而多样性从无效开始（空袋不包含 5 个不同的项目）。
首先要注意的是，对于附加约束，您需要一个无效/不可解的概念，因为如果没有 5 个不同的项目满足权重约束，则没有解决方案。
一旦你定义了一种方法来 return 一些 invalid 结果，它真的很接近标准背包问题。在递归中，只需传递剩余的允许权重和当前多样性。在recursion anchor的情况下，检查Diversity，如果Diversity不满足要求，则return invalid，否则return结果和普通背包问题一样。检查 invalid 的递归结果并相应地处理它。