嵌套长度算法 [英] Nesting lengths Algorithm

问题描述

大家好，


我对长度嵌套有疑问，请向我建议解决此问题的最佳方法.我的问题如下.

我有一些标准长度，可以说总长度(这是我们需要用一些特定长度的块填充的总长度)

输入是长度块的列表，例如:5000、4000、3000 .....

每个块之间的间隙范围是例如200到500(可以在该范围内调整该间隙)

现在，我们必须用上述可用的长度块填充总长度，并在每个块之间填充间隙，并且该间隙应在上述给定的间隙范围内.



请建议我一些解决此问题的方法.

在此先感谢...

此致
Anil

Hi All,


I have a problem with nesting of lengths please suggest me the best way of solving this. my problem is as follows.

I have some standard length lets say Total length (This is the total length which we need to fill with some specific length blocks)

input is list of length blocks eg: 5000, 4000, 3000 .....

and gap between each block is a range eg: 200 to 500 (this gap can be adjusted with in the range)

Now we have to fill the Total length with the above available length blocks with gap between each block and that gap should be with in the gap range given above.



Please suggest me some way of solving this problem.

Thank in advance...

Regards,
Anil

推荐答案

假设您拥有
-总长度L _total
-n个变长段S _i
的列表 -[G _min ... G _max ]
范围内的可能差距
如果您没有其他限制(例如，并非所有段都需要放置，并且任何大小的间隙都可以保留在末尾)，则开始随机填充(或从头到尾)并保留G <sub>min
这是一个显而易见的解决方案，但可能还不够好.

如果必须检查所有段都必须放置且不允许尾随间隙的可能解决方案，则可以计算最佳情况与最坏情况:
1)所有段的总和:S total = ∑ S i
2)所有差距的余地:G total = L total -S total
3)最小间隙:G total(min) =(n-1)x G min
4)最大差距:G total(max) =(n-1)x G max

5)如果G total(min)≤G total ≤G total(max)

6a)如果可以，平均间隔G av = G 总计/(n-1)
7a)如果可以，将一个片段S i 放在另一个片段之后，并在它们之间放置间隙G av .

6b)如果不正确，则出现错误.

干杯
安迪</sub>

Assuming you have
- a total length L_total
- a list of n varying length segments S_i
- possible gaps in the range of [G_min...G_max]

If you have no further constraints (e.g. not all segments need to be placed, and any size of gap can remain at the end), then start to fill randomly (or from begin to end) and leave a G_min between each segement. Stop when there is no segment left or when the next segment can not be placed any more.

This is an obvious solution, but maybe not good enough.

If you have to check for the possible solution where all segments must be places and no trailing gap is allowed, then you calculate the best versus worst case:
1) Sum of all segments: S_total = ∑ S_i
2) Room for all gaps: G_total = L_total - S_total
3) Minimal gaps: G_total(min) = (n-1) x G_min
4) Maximal gaps: G_total(max) = (n-1) x G_max

5) ok if G_total(min) ≤ G_total ≤ G_total(max)

6a) if ok, average gap G_av = G_total / (n-1)
7a) if ok, place one segment S_i after the other and place gap G_av in between.

6b) if not ok, error.

Cheers
Andi

这篇关于嵌套长度算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！