w****x
发帖数: 2483 | 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*****y
发帖数: 1071 | 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****x
发帖数: 2483 | 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****x
发帖数: 2483 | 4
是吗，看来想当Googler还是得看CLRS啊，我发现很多Google的题都是CLRS的，真TM麻
烦
【在 j*****y 的大作中提到】
: 这是 clrs的一道习题 :)
| p*****2
发帖数: 21240 | 5
为什么一定要进Google？
【在 w****x 的大作中提到】
:
: 是吗，看来想当Googler还是得看CLRS啊，我发现很多Google的题都是CLRS的，真TM麻
: 烦
| w****x
发帖数: 2483 | 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****x
发帖数: 2483 | 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*****y
发帖数: 1071 | 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****x
发帖数: 2483 | 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****x
发帖数: 2483 | 10
是吗，看来想当Googler还是得看CLRS啊，我发现很多Google的题都是CLRS的，真TM麻
烦
【在 j*****y 的大作中提到】
: 这是 clrs的一道习题 :)
| | | p*****2
发帖数: 21240 | 11
为什么一定要进Google？
【在 w****x 的大作中提到】
:
: 是吗，看来想当Googler还是得看CLRS啊，我发现很多Google的题都是CLRS的，真TM麻
: 烦
| w****x
发帖数: 2483 | 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******e
发帖数: 20 | 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****e
发帖数: 54598 | 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*c
发帖数: 904 | 15
章节是什么？谢谢
【在 j*****y 的大作中提到】
: 这是 clrs的一道习题 :)
| x*********w
发帖数: 533 | |
|
