所以我遇到了一个我想解决的有趣问题。当我试图解决具有不确定转换的游戏时，它遇到了。如果您听说过这个问题或知道它是否有关于它的名称/论文，请告诉我！这里是。
给定 n 个盒子和 m 个元素，其中 n1 有 i1 个元素，n2 有 i2 个元素，依此类推（即 i1 + i2 + ... + in = m）。每个元素都有一个权重 w 和值 v。从每个 n 个框（解决方案大小 = n）中找到一个元素的选择，使得该值最大化并且权重 <= k（一些输入参数）。
我注意到的第一件事是 i1*i2...*in 解决方案。这小于 m 选择 n，小于 2^m，所以这是否意味着问题在 P 中（抱歉我的数学有点模糊）？有没有人知道不涉及迭代每个解决方案的算法？近似值很好！
编辑：好的，所以这个问题实际上与背包问题相同，所以它是 NP 难的。让每个盒子有两个元素，一个是零大小和零值，另一个是非零大小和非零值。这与背包相同。谁能想到一个聪明的伪多项式时间算法/转换为背包？