盒子塔(堆叠的多维数据集) [英] tower of boxes (stacking cubes)

问题描述

我上周完成了这项任务，但找不到解决该问题的好算法.因此，这里是描述:

如果不将较大的立方体放置在较小的立方体中，或者不将较硬的立方体放置在较轻的立方体中，则可以使用构建立方体来构建稳定的塔.编写一个程序，以n个立方体的数量为您提供最高的塔数.
输入:
在in.txt的第一行中，有立方体数n(1 = 输出:
您必须将可能的最高稳定塔的m数写入out.txt.在第二行中，您必须从下到上输入塔的序号m.通过塔的高度，我们指的是所有立方体的边长的数量(而不是立方体的数量).如果解决方案不止一种，那么您可以提供所需的任何内容
输入和输出示例:
输入:
5
10 3
20 5
15 6
15 1
10 2
和输出:
3
2 1 5
这是该程序的限制.时间限制:0.2秒.内存限制:16 Mb

希望您能帮助我解决此问题.感谢所有帮助

解决方案

关系块 A 可以放在块 B 顶部"定义了部分订单.您可以使用卡恩算法(又称拓扑排序")将其转化为总计顺序，然后您可以深入遍历该顺序以找到最长的路径.. >

i got this task last week but can't find a good algorithm to solve the problem. So here is the description:

You can build a stable tower with building cubes by not putting bigger cubes to smaller ones and if you don't put harder cubes into lighter ones. Make a programme which gives you the highest possible tower with n number of cubes.
Input:
In the first row of in.txt there is the number of cubes n (1 =< n =<1000). the following n line consisting two positive integer, a cube's sidelength and weight (both of them are not higher than 2000) there are no similar cubes which sidelength and wieght is the same
Output:
you have to write the highest possible stable tower's m number into out.txt. into the second row you have to write in the ordinal number m of the tower from bottom to top. by the height of the tower we mean the amount of all of the cubes's sidelength (not the number of cubes). if there are more than one solution, you can give whatever you want
example for input and output:
input:
5
10 3
20 5
15 6
15 1
10 2
and the output:
3
2 1 5
here are limits on the program. Time limit: 0.2 sec. Memory limit: 16 Mb

I hope you can help me to solve this. thx for all help

解决方案

The relationship "block A can be placed on top of block B" defines a partial order on the blocks. You can use Kahn's algorithm (aka "topological sort") to turn this into a total order, which you can then traverse in depth order to find the longest path.

这篇关于盒子塔(堆叠的多维数据集)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！