我最近遇到了以下编程挑战：
声明
考虑一个nxn大小的2d平方矩阵，它包含0和1。你必须用1、2或3的平方覆盖矩阵中的所有1。使用1号方格的覆盖成本为2，使用2号方格的覆盖成本为4，使用3号方格的覆盖成本为7目标是找出覆盖矩阵中所有1的最小覆盖成本。
约束条件
1一般性意见
允许重叠覆盖正方形。
覆盖方格不必只覆盖1s-
它们也可以覆盖包含0的单元格。
例子
以下面的矩阵为例：
0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0
0 1 1 1 0 0 0 0
0 0 1 1 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 1 0
在上面的例子中，最小覆盖成本是7x1+4x2+2x1=17。另一种覆盖是可能的，最小覆盖成本为7x1+4x1+2x3=17。
我的方法
我试图用以下方式解决这个问题：
当3x3区域中的1个数大于等于5时，使用3号正方形覆盖1从矩阵中去掉那些1。
下一步，使用2号正方形覆盖1，其中任何2x2中有1个
面积大于等于2。从矩阵中去掉那些1。
用1号方格纸盖住剩余的1号。
这种方法是贪婪的，不是最优的对于上面的例子，我的方法给出的答案是7x1+4x2+2x2=19，这不是最优的。
任何关于如何处理这个问题的指针，或者可以用来解决这个问题的已知问题的引用都是值得赞赏的。谢谢。
更新
根据@bvdb answer的提示，我更新了方法，根据覆盖的1s数选择覆盖正方形然而，这种方法仍然不是最优的假设我们有以下安排：
1 0 1
0 0 0
1 0 1
这种安排将使用4个大小为1的覆盖方格覆盖，而它们必须使用1个大小为3的方格覆盖一般来说，3x3区域的5 1必须根据它们在该区域的分布情况使用不同的策略来覆盖我可以为所有类型的情况硬编码，但我正在寻找一个优雅的解决方案，如果它存在的话。
最佳答案
你的问题是典型的Packing problem。
你先把最大的盒子装进去的方法很有道理。
一个简单的方法让你的算法更好，只是优先选择3x3平方与最大余弦。
例子：
使用大小为3的正方形覆盖1，其中任何3x3区域中的1的数目为9。从矩阵中去掉那些1。
是的，但是面积是8。
是的，但是面积是7。
是的，但是面积是6。
下一步，使用大小为2的正方形来覆盖1，其中任何2x2区域中的1的数目为4。从矩阵中去掉那些1。
等。。。
蒙特卡罗方法
但如果你想增加重叠，那就变得更棘手了。我相信你能用数学方法解决这个问题。然而，当逻辑变得棘手时，总是会想到Monte Carlo方法：
monte carlo方法（或montecarlo实验）是一类基于重复随机抽样获得数值结果的计算算法。它们通常用于物理和数学问题，在很难或不可能使用其他数学方法时最有用。
蒙特卡罗用编码逻辑交换速度和随机性：
STEP 1: repeat 4 times:
cor = randomCoordinate()
if ( hasContent(cor, 3) ) then putSquare(cor, 3)
STEP 2: repeat 16 times:
cor = randomCoordinate()
if ( hasContent(cor, 2) ) then putSquare(cor, 2)
STEP 3: corList = getFreeSquaresWithContent()
putSquare(corlist, 1)
calculateScore()
store used squares and score.
这段代码应该很简单，但是非常快。
然后跑10万次，保持前10名。
获胜者最常使用哪一个3x3正方形？
将此信息用作“起始位置”。
现在，使用这个起始位置从步骤2再次运行它。
这意味着100.000次迭代不再需要关注3x3的正方形，它们立即开始添加2x2的正方形。
注：你所做的迭代次数（例如100.000次）实际上是一个所需响应时间和所需精度的问题你应该测试一下，看看什么是可以接受的。
关于algorithm - 二维矩阵中的最佳正方形覆盖(最大限度地减少覆盖成本)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29891569/