二维背包或正方形包装的变体

Question

我正在处理一个优化问题，我把它归类为组合问题。现在，我知道这是背包问题的2D变体，但请您理解我的意思：

如果我有一个由等号单元格组成的网格，那么如何在这个网格区域放置一定数量的不同大小的正方形物体，如果每个对象都有它的成本和效益，并且目标是排列具有最大收益/成本比的对象：

• 目标1: 1x1平方，成本= 800，value= 2478336
• 对象2: 2x2平方cost= 2000值= 7565257
• 目标3: 3x3平方cost= 3150 value= 14363679

目标3有最好的值/成本比，所以这个方法是一个贪婪的方法，首先要尽可能多地放置更大的平方，但是仍然有许多最优解取决于面积的大小。

此外，正方形物体不能重叠。我用R来做这个，软件包adagio对单个和多个背包都有算法，但是对于2D背包问题没有算法。因为我在优化和编程方面很新，所以我不确定是否有办法用R来解决这个问题，有人能帮忙吗？谢谢!

Answer 1

首先，我不是R和柔板方面的专家。其次，我认为您的问题并不完全是2d背包，它看起来像包装问题的一个变体，所以它需要一种不同的方法。

因此，首先，检查一下R优化包的清单，特别是下面几节：

1. 优化中的特定应用程序(例如，禁忌搜索可能对您有用)
2. 开源优化器的数学编程求解器/接口(艾普苏绝对可以解决您的任务)
3. 全局和随机优化(其中一些包可用于解决任务)

如果您不与R绑定，请将米尼辛视为一个求解器。它非常容易安装/使用，并且在内存/时间消耗方面非常有效。此外，有许多很好的例子，如何使用它。