最小化框和最大化对象的算法

Question

一个框包含 3 个数字属性。属性是最大总(普通+稀有)对象、最大普通对象、最大稀有对象。现在让我们举个例子，我有 4 个盒子。

• 框 1:最多 5 个总对象，最多 4 个普通对象，最多 2 个稀有对象。
• 方框 2:最多 10 个，最多 9 个正常，最多 3 个稀有。
• 框 3:最多 8 个，最多 5 个正常，最多 4 个稀有。
• 方框 4:最多 4 个，最多 4 个正常，1 个最多稀有。

现在我必须将 8 个普通元素和 5 个稀有元素放入这些盒子中。

我可以使用的最少盒子数量是多少？它们是什么盒子？以编程方式，我可以通过蛮力/递归搜索来实现这一点。找出所有可能的盒子组合后，我会根据盒子中浪费的最少空间对数组/列表进行排序。是否有更高效的编程或数学方法来找出要使用的最小框数？

Answer 1

我认为一个有效的方法是:
假设你有“n”个盒子，“a”个普通物体和“b”个稀有物体，a>b。

1. 根据普通对象中的最大空间属性对列表中的所有框进行排序。调用此列表 X。
2. 根据属性最大值对另一个列表中的所有框进行排序。稀有物体中的空间。调用此列表 Y。
3. 从 a>b 开始，填充列表 X 中最大的框。
4. 检查是否 a(剩余)> b(剩余)，如果是，则将它们放入列表 X 中的下一个最大框，否则将它们放入列表 Y 中的下一个最大框(如果填充的框也是列表 Y 中最大的框)。
5. 继续这样做直到a和b都为0。

虽然这不会总是为所有情况提供确切的最小框数，但通常可以很好地处理大量框。