r - 二维背包或方形包装的变体

Question

我正在处理一个优化问题，我将其归类为组合问题。现在，我知道这是背包问题的二维变体，但请耐心等待:

如果我有一个区域被建模为由相同大小的单元格组成的网格，如果每个对象都有其成本、 yield 和目标，如何在该网格区域上放置一定数量的不同大小的方形对象就是对具有最大 yield /成本比的对象进行排列:

• 对象 1:1x1 正方形，成本 = 800，值(value) = 2478336

• 对象 2:2x2 平方成本 = 2000 值 = 7565257

• 对象 3:3x3 平方成本= 3150 值(value)= 14363679

对象 3 具有最佳值(value)/成本比，所以我猜该方法是一种贪婪的方法，首先放置尽可能多的较大方 block ，但仍然有许多最佳解决方案，具体取决于对象的大小地区。

此外，方形对象不能重叠。 我为此使用 R，而 adagio 包具有用于单个和多个背包的算法，但不适用于 2D 背包问题。因为我在优化和编程方面很新，所以我不确定是否有办法用 R 解决这个问题，有人可以帮忙吗？ 谢谢!

Answer 1

首先，我不是 R 和柔板方面的专家。其次，我认为你的问题不完全是 2d 背包，它看起来像 packing problem 的变体。 , 因此需要不同的方法。

所以，首先，检查这个很棒的列表 R optimization packages ，尤其是以下部分:

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

如果您不依赖于 R，请考虑 Minizinc作为求解器。它非常易于安装/使用，并且在内存/时间消耗方面非常高效。此外，还有很多如何使用它的好例子。