algorithm - 最小化 K 切割后最大组的大小

Question

Consider an N x N square of integers which you are allowed to cut vertically or horizontally K times. You want to try to minimize the largest sum in each of the resulting boxes after cutting. Print out this largest sum.

---

Bonus: print out the arrangement of cuts that gives this lowest sum.

---

Hint: Use bit manipulation

例如，假设允许你进行 2 次切割并且网格是

1 0 1 4
1 0 1 0
1 2 1 4

像这样切割:

1 0 1 | 4
1 0 1 | 0
---------
1 2 1 | 4

你可以最小化四个象限中任何一个的最大总和，你会打印出 4。

---

我注意到的第一件事是，给定最多 K 次切割，用完所有 K 次切割对你有利。

我想到的一件事是二进制搜索切割位置以最小化每个左/右半部分的总和，然后二进制搜索顶部/底部，但是如何将其扩展到超过 2 个切割？

位操作的暗示也让我认为一些使用位掩码的动态编程是预期的解决方案。

有什么想法吗？

Answer 1

一个观察结果是，切割的顺序不会影响最终结果。

因此，使用位掩码，我们可以检查水平和垂直切割的每个组合。

假设我们有一个 N - 1 位的数字，表示所有水平切割，并且如果位置 ith<​​ 的位是 1，那么，这也意味着我们在之间进行了切割第 第 行和第 i + 1 行。

同样，我们可以用一个数字来表示所有的垂直切割。从这两个数字，我们可以计算出这些切割所定义的每个区域的最大总和。

用于说明我的解决方案的代码。

for(int i = 0; i< (1<< (N - 1)); i++)
  for(int j = 0; j < (1 << (N - 1)); j++)
      if(number of bit set i + j == k)
         calculate the maximum sum;