7-29 修理牧场
发布时间
阅读量：
阅读量
总体目标是将一块长度为L的木材分成n段, 每一段分别长a₁, a₂, ..., aₙ. 每次切割所产生的费用与其所切木材的总长度相等.
例如，在这个例子中：
- 将一根长度为20的木材分割成长度分别为8、7及5的小段。
- 第一次切割耗费的成本是... 由于每次切割都会产生一定的损耗（即...），所以每一次切割都需要单独计算成本。
- 在第一次切割后得到了两根小木材：其中一根长... 另一根则较长（即...）。
- 第二次切割时所使用的木材来自第一次切割后的较长小木材（即...），因此在第二次切割时也需要考虑这部分损耗（即...）。
- 最终计算得出两次切割总共耗费的成本是34元
最初采用了错误的方式进行计算，在排序后通过递归的方式切割木板，并且尽可能均匀地将每块木板切分为两段。
#include <cstdio>
#include <algorithm>
int a[10001];
int total=0;
int cal( int L, int H, int length)
{
int num = H-L; //这个区间有几段木头
if( num == 3) return a[L] + a[L+1] + length;
if( num == 2) return length;
if( num <= 1) return 0;
int mid, leftLen=0;
for( mid=L; mid<H && leftLen<length/2; mid++ )
leftLen += a[mid];
if ( leftLen > (a[mid-1]+length)/2)
{
mid--;
leftLen -= a[mid];
}
return length+ cal(L, mid, leftLen) + cal(mid, H, length - leftLen);
}
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
{
scanf("%d", a+i);
total += a[i];
}
std::sort( a, a+n );
printf("%d\n", cal( 0, n, total) );
return 0;
}
/* 测试例子
7
1 2 3 4 5 6 9
45. 8
1 1 1 1 1 1 1 1
48. 6
6 6 6 9 9 9
51. 6
6 6 7 9 9 9
*/该方法仅能近似地获得最优解，在大多数情况下可获得最优解；然而，在某些情况下无法实现这一目标；例如
6
6 6 7 9 9 9
最佳应该是 120，第一步切分为 6679，99。
但是按照上面的代码会得到122，因为第一步为了尽量均匀，木板被切为 667， 999。
那么最佳的方法是什么？哈夫曼树非叶节点求和。
在计算总开销时，在过程中观察到每块小木板长度都被重复一次，直至最终成为单一木板。
这个过程与哈夫曼树构建方法具有高度相似性。 在哈夫曼编码中所使用的木板长度参数即等同于叶子节点所对应的权值大小。 在哈夫曼树构建过程中规定，在同一层结构中拥有较大权值的节点应当位于靠近根节点的位置。
上面的代码是自顶向下的，从完整的木板开始逐步切分。
哈夫曼的做法是从下往上进行操作，在每一次操作中都选取最小的两片木材进行组合成一个稍大的木材，直到剩下一块木材为止。
用最小堆就好了。
#include <cstdio>
#include <algorithm>
int a[10001];
int total=0, size;
void adjust( int cur, int n )//这个操作，把堆中cur位置元素下沉到合适位置
{
int child= cur*2+1, tmp = a[cur];
while( child < n ) //还有子的时候才需要调整
{
if( child+1 < n && a[child+1] < a[child] )
child++;
if( a[child] < tmp ) //这里还有一种写法，不停的swap(cur, child), 无需在循环外填上tmp
{
a[cur] = a[child];
cur = child;
child = cur*2+1;
}
else
break;
}
a[cur] = tmp;
}
void minheapify( int n)
{
for( int i=n/2; i>=0; i-- ) //这地方 n/2 还是 n/2-1? N/2保险一点。。
adjust( i, n);
}
void replace(int n, int v)
{
a[0] = v;
adjust(0, n);
}
void pop(int &size)
{
a[0] = a[--size];
adjust(0, size);
}
int calWPL( ) //哈夫曼树的weight path length
{
int ret=0, length=0;
while( size > 1 )
{
length = a[0];
pop(size);
length += a[0];
ret += length;
//printf("%d %d %d %d==========\n", size, length, length-a[0], a[0]);
replace( size, length);
}
return ret;
}
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", a+i);
//std::sort( a, a+n ); //排序其实是nlogn建堆的方法
minheapify(n);
size = n;
printf("%d\n", calWPL( ) );
return 0;
}全部评论 (0)
还没有任何评论哟~