做了一下Google的切木头 - 未名空间MITBBS历史存档

w*x2013-01-26 08:01

1 楼

//least cost to cut a batten
//the cost of cutting each segment is the cost of the segment length, an
array is storing each end point, eg:
// [0, 3, 7, 8, 11, 12], the batten length is 12, there are 4 cuting point
//No greedy solution to this problem
int getMinCost(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
int rec[100][100] = {0};

for (int i = 2; i < n; i++)
{
for (int j = 0; j < n-i; j++)
{
int nMin = INT_MAX;
for (int k = 1; k < i; k++)
nMin = min(nMin, rec[j][j+k] + rec[j+k][j+i] + a[j+i] - a[j]
);

rec[j][j+i] = nMin;
}
}
return rec[0][n-1];
}
代码不长，很容易出错，这几行code出了3个错

j*y2013-01-26 08:01

2 楼

这是 clrs的一道习题 :)

【在 w****x 的大作中提到】

: //least cost to cut a batten
: //the cost of cutting each segment is the cost of the segment length, an
: array is storing each end point, eg:
: // [0, 3, 7, 8, 11, 12], the batten length is 12, there are 4 cuting point
: //No greedy solution to this problem
: int getMinCost(int a[], int n)
: {
: if (NULL == a || n <= 1)
: return -1;
: int rec[100][100] = {0};

w*x2013-01-26 08:01

3 楼

后来想了一下是不是可以用greedy算法来做，仔细分析了一下发现不可行，果然写了一
个不能得到最优解。
int _inner_greedy(int a[], int n)
{
if (n <= 2)
return 0;
int nMinIndex = 1;
for (int i = 1; i < n-1; i++)
{
if (abs((a[i] - a[0]) - (a[n-1] - a[i])) < abs((a[nMinIndex] - a[0])
- (a[n-1] - a[nMinIndex])))
nMinIndex = i;
}
return a[n-1] - a[0] + _inner_greedy(a, nMinIndex+1) + _inner_greedy(a+
nMinIndex, n-nMinIndex);
}
int getMinCostGreedy(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
_inner_greedy(a, n);
}
test case:
int a[] = {0, 1, 2, 3, 7, 8, 11, 12, 14, 19, 25, 26, 30, 38, 49};
cout<cout<

w*x2013-01-26 08:01

4 楼

是吗，看来想当Googler还是得看CLRS啊，我发现很多Google的题都是CLRS的，真TM麻
烦

【在 j*****y 的大作中提到】

: 这是 clrs的一道习题 :)

p*22013-01-26 08:01

5 楼

为什么一定要进Google？

【在 w****x 的大作中提到】

:
: 是吗，看来想当Googler还是得看CLRS啊，我发现很多Google的题都是CLRS的，真TM麻
: 烦

w*x2013-01-26 08:01

6 楼

打印版本，真难做对：
int printMinCost(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
int recCost[100][100] = {0};
int recSplit[100][100] = {0};

for (int i = 2; i < n; i++)
{
for (int j = 0; j < n-i; j++)
{
int nMin = INT_MAX;
int nSplitIndex = 1;
for (int k = 1; k < i; k++)
{
int nCost = recCost[j][j+k] + recCost[j+k][j+i] + a[j+i] - a
[j];
if (nCost < nMin)
{
nMin = nCost;
nSplitIndex = j+k;
}
}

recCost[j][j+i] = nMin;
recSplit[j][j+i] = nSplitIndex;
}
}
stack> stk;
stk.push(std::make_pair(0, n-1));
while (!stk.empty())
{
int nLft = stk.top().first;
int nRgt = stk.top().second;
int nCost = recCost[nLft][nRgt];
int nSplit = recSplit[nLft][nRgt];
stk.pop();
if (nCost == 0)
continue;
cout<stk.push(make_pair(nSplit, nRgt));
stk.push(make_pair(nLft, nSplit));
}
return recCost[0][n-1];
}

w*x2013-01-26 08:01

7 楼

//least cost to cut a batten
//the cost of cutting each segment is the cost of the segment length, an
array is storing each end point, eg:
// [0, 3, 7, 8, 11, 12], the batten length is 12, there are 4 cuting point
//No greedy solution to this problem
int getMinCost(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
int rec[100][100] = {0};

for (int i = 2; i < n; i++)
{
for (int j = 0; j < n-i; j++)
{
int nMin = INT_MAX;
for (int k = 1; k < i; k++)
nMin = min(nMin, rec[j][j+k] + rec[j+k][j+i] + a[j+i] - a[j]
);

rec[j][j+i] = nMin;
}
}
return rec[0][n-1];
}
代码不长，很容易出错，这几行code出了3个错

j*y2013-01-26 08:01

8 楼

这是 clrs的一道习题 :)

【在 w****x 的大作中提到】

: //least cost to cut a batten
: //the cost of cutting each segment is the cost of the segment length, an
: array is storing each end point, eg:
: // [0, 3, 7, 8, 11, 12], the batten length is 12, there are 4 cuting point
: //No greedy solution to this problem
: int getMinCost(int a[], int n)
: {
: if (NULL == a || n <= 1)
: return -1;
: int rec[100][100] = {0};

w*x2013-01-26 08:01

9 楼

后来想了一下是不是可以用greedy算法来做，仔细分析了一下发现不可行，果然写了一
个不能得到最优解。
int _inner_greedy(int a[], int n)
{
if (n <= 2)
return 0;
int nMinIndex = 1;
for (int i = 1; i < n-1; i++)
{
if (abs((a[i] - a[0]) - (a[n-1] - a[i])) < abs((a[nMinIndex] - a[0])
- (a[n-1] - a[nMinIndex])))
nMinIndex = i;
}
return a[n-1] - a[0] + _inner_greedy(a, nMinIndex+1) + _inner_greedy(a+
nMinIndex, n-nMinIndex);
}
int getMinCostGreedy(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
_inner_greedy(a, n);
}
test case:
int a[] = {0, 1, 2, 3, 7, 8, 11, 12, 14, 19, 25, 26, 30, 38, 49};
cout<cout<

w*x2013-01-26 08:01

10 楼

是吗，看来想当Googler还是得看CLRS啊，我发现很多Google的题都是CLRS的，真TM麻
烦

【在 j*****y 的大作中提到】

: 这是 clrs的一道习题 :)

p*22013-01-26 08:01

11 楼

为什么一定要进Google？

【在 w****x 的大作中提到】

:
: 是吗，看来想当Googler还是得看CLRS啊，我发现很多Google的题都是CLRS的，真TM麻
: 烦

w*x2013-01-26 08:01

12 楼

打印版本，真难做对：
int printMinCost(int a[], int n)
{
if (NULL == a || n <= 1)
return -1;
int recCost[100][100] = {0};
int recSplit[100][100] = {0};

for (int i = 2; i < n; i++)
{
for (int j = 0; j < n-i; j++)
{
int nMin = INT_MAX;
int nSplitIndex = 1;
for (int k = 1; k < i; k++)
{
int nCost = recCost[j][j+k] + recCost[j+k][j+i] + a[j+i] - a
[j];
if (nCost < nMin)
{
nMin = nCost;
nSplitIndex = j+k;
}
}

recCost[j][j+i] = nMin;
recSplit[j][j+i] = nSplitIndex;
}
}
stack> stk;
stk.push(std::make_pair(0, n-1));
while (!stk.empty())
{
int nLft = stk.top().first;
int nRgt = stk.top().second;
int nCost = recCost[nLft][nRgt];
int nSplit = recSplit[nLft][nRgt];
stk.pop();
if (nCost == 0)
continue;
cout<stk.push(make_pair(nSplit, nRgt));
stk.push(make_pair(nLft, nSplit));
}
return recCost[0][n-1];
}

l*e2013-01-26 08:01

13 楼

没看都题目，可以再详细解释一下题目要求吗？
要把batten cut 成什么样子？
还有rec[i][j] 代表什么？

【在 w****x 的大作中提到】

: //least cost to cut a batten
: //the cost of cutting each segment is the cost of the segment length, an
: array is storing each end point, eg:
: // [0, 3, 7, 8, 11, 12], the batten length is 12, there are 4 cuting point
: //No greedy solution to this problem
: int getMinCost(int a[], int n)
: {
: if (NULL == a || n <= 1)
: return -1;
: int rec[100][100] = {0};

z*e2013-01-26 08:01

14 楼

我是进来看签名的

【在 w****x 的大作中提到】

: //least cost to cut a batten
: //the cost of cutting each segment is the cost of the segment length, an
: array is storing each end point, eg:
: // [0, 3, 7, 8, 11, 12], the batten length is 12, there are 4 cuting point
: //No greedy solution to this problem
: int getMinCost(int a[], int n)
: {
: if (NULL == a || n <= 1)
: return -1;
: int rec[100][100] = {0};

y*c2013-01-26 08:01

15 楼

章节是什么？谢谢

【在 j*****y 的大作中提到】

: 这是 clrs的一道习题 :)

x*w2013-01-26 08:01

16 楼

咳咳..