先说条件固定宽度W，我觉得这个问题不难解决，因为要求中只说了保证长宽比不变，所以只要将图片拼接成矩形，再对所有图片进行缩放就可以满足任意要求的宽度了。
现在问题就变成了如何将图片拼接成矩形。我觉得这个问题其实是多解的，任意多张图片通过缩放都可以拼成一个矩形。现在问题是为了让图片美观我们要做一下分类，根据长宽比把瘦高类图片分为一组（本例中的那颗树），把矮胖类图片分为一组（本例中的其他5张图片），然后尽量将瘦高类的图片横排，矮胖类的图片竖排，将他们同组的排列成矩形，这样分组的目的是让同一类图片尽力合理的占用空间。
剩下的问题是如何进行两组之间的组合，我觉得虽然题目中没有要求，但是这里出于美观考虑，应该设定一个规定参数，比如每行两张图片。如果没有规定可能会出现1张瘦高在上5张矮胖在下的情况，显然不够美观。瘦高类图片由于是横排，所以每张都占一个位置，矮胖类图片不管有多少，由于是竖排，所以在宽度上面只占一个位置。本例中瘦高类只有一颗树，所以正好满足每行两个的要求，也就出现了瘦高类和矮胖类横排的结果，如果瘦高类图片很多，比如有10张，可以根据规定参数（比如每行2个），进行切分，多出来的再自行分组对齐（矮胖瘦高的分组缩放规则不变），换行显示。同样在高度方面也应该有一个固定的参数，比如规定每列最多竖排3个图片，如果没有规定那本例来说，可能会出现5张图片横排在左，右边一颗大树。有了规定，多余的图片将自行分组对齐（矮胖瘦高规则不变），如本例3个一组排在大树左边，多于的应该和多于的竖高类图片再进行左右组合，但由于没有竖高类图片了，所以竖排在下，但是由于每行2个图片的规定，这次破例再对他们进行横排对齐。
总的来说将图片缩放成固定宽度以及将图片排列成矩形并不困难，问题是如何尽力美观的将他们排列起来，何所谓美观？就是尽量让图片间的占空间比例相等，而分组和固定参数是解决这个问题的方法。这里举两个极端的例子，假如图片是4个正方形，2x2排列无论如何缩放，在宽度和高度上都是相等的所以它是最完美的。另一个例子，一个横条和一个竖条排列，无论如何排列，占空间比例都不可能做到很好的均匀分配，所以最后必定是一个图片放大的都失真了，另外一个却缩小的看不见人了。
至于两个固定参数的选择我觉得和图片的比例分配有关系，应该也可以通过算法让计算机自己推断，这个现在还没想好，但是感觉如果不出现特别极端的情况，一般人工设定两个数值，比如本例的2和3，应该就可以解决日常问题了。
再有说一句题外话，假如既规定了最后的宽度又规定了高度，问题可就难解决多了，以前好像看到过类似的问题。 :D $支持$
还是楼上分析的专业，不知道算法里是否有个专门的领域研究排版的，估计报社什么的应该常用这些东西。另外小声问一句，楼主是学那门课遇到这个问题的？我在德国还没开始上专业课呢，不过也快了，不知道以后学习中是否也会碰到这些问题，德国大学好像专门有个算法课吧，是master的还是bachelor的？ 楼主题目正确么??
你的答案是两张图片只能横排,
举个例子,比如k=2
w=10
两张图片都是长宽比都是7:2的话(length=7,width=2),
那么横排也排不开两张呀??????!
因为w=10
而7+7=14>10
怎么可能横排呀????
俺还是没明白!$郁闷$ 原帖由 漂去漂来 于 2007-3-26 01:10 发表 http://www.dolc.de/forum/images/common/back.gif
W单位是pixel
另外，我写的也不是答案，只是我思考的一些结果。我也不知道答案是什么。
如果你设置w=500
4个横排的,
3个竖排的,
4个横排的你先选前4个图片,
3个竖排的你先选前3个图片,
然后你看结果.
如果
4个横排列的你选从第二个开始选4个,
3个竖排列的你选从第二个开始选3个,
你在看结果.
就这样一直到最后,
你看看什么乱七八糟的排列都能出来.
;) ;)
[ 本帖最后由 jeanie 于 2007-3-26 08:56 编辑 ] 我觉得这个问题好像很大，应该算是算法中的一类典型问题，我刚才用google搜了一下“排版 算法”搜到好多结果，而且也都是很复杂的算法。看来真要研究起来，要翻几本书了。$汗$
这里有个用二叉树的算法，还没看，不过估计要研究一阵了。。。
http://scholar.ilib.cn/Abstract.aspx?A=gctxxb200503033
[ 本帖最后由 cn1h 于 2007-3-26 10:33 编辑 ] 原帖由 漂去漂来 于 2007-3-26 01:10 发表 http://www.dolc.de/forum/images/common/back.gif
W单位是pixel
另外，我写的也不是答案，只是我思考的一些结果。我也不知道答案是什么。
应该解决了!
第一种:
结果:
最后排完肯定能排成一个矩形(当然也可以排成乱七八糟的形状,但那样不美观),
想法:
不管给多少个横的竖的图形,都可以用1横,1竖,多横,多竖来表示
比如给定19999999999999999999999999999999999999999个图形(其中包括199999999999999999999个横的,剩下的都是竖的话)
可以用1横1竖来排(因为1横1竖排列出来的肯定是矩形),然后横的没有了,剩下很多竖的剩下那些竖的肯定也能排成一个矩形,无非是每行图行多少罢了.
在把两个矩形逻起来,还是个矩行.(因为他的图片缩放大小,简单的是不管w是多少,要先排列完了,然后整体缩放,来调整的给定的w大小)
第二种:
可以稍微复杂点,
把给定3横,1竖的情况,两横两竖,3竖1横,2横1竖.....那些特殊点的情况单独提取出来,每个情况作为一个object,
然后把给定的19999999999999999999999999999999999999999图形分解成那些个情况的组合,因为上面那些情况都是一个矩型,
所以同样也是很多矩形罗列起来,组成一个大的矩形罢了,
如果转换成代码应该也不是太困难,(因为俺现在刚学到if选择语句的应用,所以没写代码)
特别是第一种更简单,而且满足要求应该,
这题营养不大,或者是要求不明确.(个人感觉)$汗$ $汗$
[ 本帖最后由 jeanie 于 2007-3-26 12:29 编辑 ] 我觉得未必两张照片也未必一定要并列横排
因为两张倘若是非常扁的那种照片的话并列横排的话会肯定很丑陋
我觉得还有一点就是尽量保持原图的大小不作缩放，或者说对尽量少的图片作尽量小的缩放
或者按照客户的意见来。。。 这个跟适不适合学 info 有什么关系，
你们以上解决的都是已知多少个图片， 用图片来定算法， 而不是算法适用于多少个图片，
还有， 这属于数学建模上的问题， 如果没有学过运筹学这门课， 这些东西当然不能说出个道道来了，
计算机有多少个方向啊，难道这么简单就判断谁适合谁不适合学了吗， 每个人都有很大的潜力，
建议如果 lz想讨论一下， 就直接发讨论贴好了， 但不要这么说而希望高手看到进来挑战一下你的难题。
ps,有打击其他人的嫌疑 感觉挺难的，，，，， 原帖由 漂去漂来 于 2007-3-26 16:57 发表 http://www.dolc.de/forum/images/common/back.gif
回复 cn1h
这个问题叫它”排版”我看只是广义上的。比方Latex和word类程序，各有千秋。
具体问题具体分析的话，jeanie 说的第2种情况是个很不错的解决办法，至少在我测试的程序中还是有不错的效果，不过感觉 ...
客户的要求怎么能不考虑呢？那最简单的算法莫过于把所有图片缩放到宽度都为W，一列列下来，alles ok，那样算法没错吧？问题能漂亮了么？这和只为了版面而不考虑原先风格而把图片缩放拼凑在一起也没什么太大区别吧？ 原帖由 漂去漂来 于 2007-3-26 02:32 发表 http://www.dolc.de/forum/images/common/back.gif
趁周末实验了测试版。
这里可以实验，有些情况下有写缺憾：
补充，在Firefox1.5+ 下测试，但未对IE经行优化可能会出现显示偏差
http://toothy.csuchen.de/layout/index.php
http://toothy.csuchen.de ...
5张竖版的还有些问题，而且选的照片是横竖显示比例完全一样的啊，当多几种显示比的时候能实现么？aber schon gut！ $kiss$ 俺跟着你学 $支持$ $支持$ $支持$
简单的说来就是随机选择3到4张图片（或按照用户要求的最小略缩图大小和版式宽度）作为一行。然后先调高度，再调宽度$考虑$ $考虑$
[ 本帖最后由 数字蛋糕 于 2007-4-5 11:53 编辑 ]
页:
[1]