B*******1
发帖数: 2454 | 1 似乎是很久以前有个google面筋里面的，
一个矩形，怎么分成最少的正方形啊，知道用dp，但是又不知道从何处入手。 |
f*******t
发帖数: 7549 | |
B*******1
发帖数: 2454 | 3 可以给个例子吗？
譬如 4 * 7
thanks |
v*****k
发帖数: 7798 | |
B*******1
发帖数: 2454 | 5 一言惊醒梦中人，呵呵。
thanks。
【在 v*****k 的大作中提到】
: 这个不是背包问题么？
|
a*******6
发帖数: 520 | 6 怎么觉得应该用opt[a, b]来表示a*b的矩形上的最优解，然后考虑从中挖掉一个正方形
，然后考虑各种情况下的子问题（的和）
怎么背包，说来听听啊～
【在 B*******1 的大作中提到】
: 一言惊醒梦中人，呵呵。
: thanks。
|
b******g
发帖数: 1721 | 7 怎么回事？能否说明一下？
【在 B*******1 的大作中提到】
: 一言惊醒梦中人，呵呵。
: thanks。
|
B*******1
发帖数: 2454 | 8 我回头想了，觉得挺难套背包上去的，因为这2维的，2边都要fit，请vanmark 指教啊
啊。 |
v*****k
发帖数: 7798 | 9 谈不上指教啊，我也就是随便那么一想。最好吧原题写一下？
【在 B*******1 的大作中提到】
: 我回头想了，觉得挺难套背包上去的，因为这2维的，2边都要fit，请vanmark 指教啊
: 啊。
|
a*******6
发帖数: 520 | 10 同意，又想了一下如果对切正方形的规则不做限定的话（比如说一刀切到底之类的），
这个问题可能很难（贪心和动态规划都有问题）～ 放下原题吧
【在 v*****k 的大作中提到】
: 谈不上指教啊，我也就是随便那么一想。最好吧原题写一下？
|
|
|
g**********y
发帖数: 14569 | 11 if x>y dp[x][y] = 1 + dp[x-y][y]
else if x==y return 1;
else // x
dp[x][y] = 1 + dp[x][y-x] |
B*******1
发帖数: 2454 | 12 dp[x][y] = 1 + dp[x-y][y]
这个一定成立吗？ 要不要证明一下？
【在 g**********y 的大作中提到】
: if x>y dp[x][y] = 1 + dp[x-y][y]
: else if x==y return 1;
: else // x: dp[x][y] = 1 + dp[x][y-x]
|
a*******6
发帖数: 520 | 13 这是有问题的，如果是6*7的rectangle，你这个得到的答案是7
实际上5个正方形就够了
【在 g**********y 的大作中提到】
: if x>y dp[x][y] = 1 + dp[x-y][y]
: else if x==y return 1;
: else // x: dp[x][y] = 1 + dp[x][y-x]
|
g**********y
发帖数: 14569 | 14 这个指正好，谢谢。我去想想。
【在 a*******6 的大作中提到】
: 这是有问题的，如果是6*7的rectangle，你这个得到的答案是7
: 实际上5个正方形就够了
|
g**********y
发帖数: 14569 | 15 public class SquareSplit {
private int[][] dp;
public int minSquares(int w, int h) {
int a = Math.min(w, h);
int b = Math.max(w, h);
dp = new int[a+1][b+1];
for (int i=0; i<=b; i++) {
dp[0][i] = 0;
dp[1][i] = i;
}
for (int i=2; i<=a; i++) {
for (int j=0; j<=b; j++) {
dp[i][j] = -1;
}
}
return calc(a, b);
}
private int calc(int w, int h) {
int a = Math.min(w, h);
int b = Math.max(w, h);
if (dp[a][b] >= 0) return dp[a][b];
int min = Integer.MAX_VALUE;
for (int i=1; i<=a; i++) {
min = Math.min(min, 1 + calc(a-i, i) + calc(a, b-i));
min = Math.min(min, 1 + calc(b-i, i) + calc(a-i, b));
}
dp[a][b] = min;
return min;
}
} |
q****x
发帖数: 7404 | 16 听起来像经典算法。
【在 B*******1 的大作中提到】
: 似乎是很久以前有个google面筋里面的，
: 一个矩形，怎么分成最少的正方形啊，知道用dp，但是又不知道从何处入手。
|
a*******6
发帖数: 520 | 17 和我之前想的dp一样，不过还是有点问题，我也不能证明他是对的
基本想法是把左上角的正方形拿掉后reduce到两个子问题上，但是还是有个东西需要证明
比如说下面这个例子：
xx****
xx**zz
*yyyzz
*yyy**
*yyy**
假设在最优解里x,y,z是三个正方形
“for (int i=1; i<=a; i++) {
min = Math.min(min, 1 + calc(a-i, i) + calc(a, b-i));
min = Math.min(min, 1 + calc(b-i, i) + calc(a-i, b));
}” 这一步实际上是枚举x正方形的大小
但是有可能把x正方形拿掉后剩余的正方形们并不能align成两个rectangles
当然如果能证明这样的情况不会发生，这个动态规划就是对的
【在 g**********y 的大作中提到】
: public class SquareSplit {
: private int[][] dp;
: public int minSquares(int w, int h) {
: int a = Math.min(w, h);
: int b = Math.max(w, h);
: dp = new int[a+1][b+1];
: for (int i=0; i<=b; i++) {
: dp[0][i] = 0;
: dp[1][i] = i;
: }
|
