挑战你的大脑！！一道有些难度的图形问题！

class Polygon{
    ...
};
class Rectangle public Polygon{
    ...
};Rectangle* Rec=new Rectangle[NUM];Stack stack;while(!stack.override){
    //generate p &n in some way
    Polygon tmp=Merge(Rec[p],Rec[n]);
    long amount=CaculateNew(Rec);
    if(amount<outcome)
        stack.push(p,n);
    else
        stack.pop();
}//没有找到好的方法，穷举不可取；
//需先证明一些定理，以避免无用计算

to zhizhi()　
想用程序把若干个大小不等的图像文件合成到一张大图以减少文件头的开销.
因为图都很小,因此文件头对图像文件尺寸的影响比较显著.

用贪婪法。1、找出面积最大的小矩形Rect1；
2、从剩余小矩形中找出面积最大的小矩形Rect2；
3、找出包含Rect1和Rect2的面积最小的组合矩形RectTemp；
　　——思路是在Rect1边长较长的一条边上贴合Rect2较长的一条边；
4、从剩余小矩形中找出RectN；
5、关键在这一步：将RectN分别与RectTemp的四个边交叠，但注意不可以与前面所有的小矩形交叠，找出面积最小的交叠矩形，并赋给RectTemp。
6、重复4、5两步直到没有剩余小矩形。第5步最难，不过也是可以实现的。主要思想是让RectN围着RectTemp的四个方向打转，穷举各个
交叠方式，找出面积最小的包围矩形RectTemp.这样虽然不见得一次就能找出最小面积的包围矩形，但如果再加上回溯法，就肯定能找出来了。
总思路就是从大到小的放置小矩形，每次放置都求最小面积。请大家指正。

shyworm(怕怕虫)的方法不可取
试想：如果最后能把所有的矩形紧密的拼成一个矩形(无间隙)
当然是它的面积最小，但这样的排列是不能用贪婪法的，它可能会涉及到运筹学方面的问
题。当然这只是我的想法，有不对之处还请多多指出。

另外，如上文说的排出的矩形可能不止一个，比如说5*12与6*10都有可能。
最好还是用starsoft007(星软)说的方法，找几个比较好的策略，然后比较策略的优先级，再按照这些策略来排列，有点像人工智能的问题了，比如说像国际象棋。
问题的确有一点难度。
谁还有更好的想法？

引用——
“想用程序把若干个大小不等的图像文件合成到一张大图以减少文件头的开销.
因为图都很小,因此文件头对图像文件尺寸的影响比较显著. ”这才是问题的出发点，因此没有必要求最优解，只要找到满意解则可。而且一般都避开这个问题：既然图像格式都是一样的，那就只保存尺寸和数据好了。然后建立一个带索引的打包文件将所有图片打包，自己写打包程序和一个载入函数就可以了。打包文件的格式可以自己定义，索引应该包含图片名称(name)、尺寸(width,height)、
起始位置(offset)（甚至可以不要offset，临时根据前面的索引累计出来）。文件格式可以是这样：索引数:　N
索引１:　Name | Width | Height
索引２:　Name | Width | Height
...
索引Ｎ:　Name | Width | Height
数据１： Color1 Color2 ...Color(Width*Height)
数据２： Color1 Color2 ...Color(Width*Height)
...
数据Ｎ： Color1 Color2 ...Color(Width*Height)作为二进制文件依次将各个图像读入即可。

TO：shyworm(怕怕虫)
啊聪~~啊聪~~啊聪明呀！

to shyworm(怕怕虫)　
因为图像文件是PNG格式，所以不能简单的只存储像素缓冲的。
而且要保证处理前和处理后的格式都是PNG……

这也可以解决：最后你得到的必然是Result.PNG这个大图，此外仍然需要一个单独的索引文件指明各个小的Src1.png ... SrcN.png分别在大图中的位置和大小。那你可以先解析PNG文件的格式，直到具备“自己用程序读写png文件”的能力。PNG文件不是可以分层的吗？你把Src1.png ...SrcN.png等小图片分别作为Result.PNG的一层就可以啦，PNG自身有压缩方式，不会浪费空间的。如果觉得生成PNG文件太麻烦，你也可以直接用FireWorks等软件直接把这些图合成一个文件（分层），然后只处理如何读取不同的图层即可。

谢谢shyworm(怕怕虫)，我回去试试，不过我怀疑目标平台（不是PC）不一定支持多层的PNG……写了一个小程序，不过有时候会产生相当糟的结果，而且因为是穷举，所以如果小图多于5就会让你失去耐心……
希望这块烂瓦能够引出大家的美玉：）
=========================================================================
import java.awt.*;
import java.awt.event.*;
import java.util.*;public class TestAlgo extends Frame {

    public TestAlgo() {
        int[][] boxesData = {{30, 40},
                         {40, 30},
                         {70, 120},
                         {200, 80},
                         {30, 20}};

        Vector boxes = new Vector();
        for (int i = 0; i < boxesData.length; i++) {
            int[] aBox = boxesData[i];
            boxes.addElement(new BoxGroup(i, aBox[0], aBox[1]));
        }
        for (int i = 0; i < boxesData.length-1; i++) {
            int loop = boxes.size();
            for (int j = 0; j < loop-1; j++) {
                BoxGroup bg1 = (BoxGroup)boxes.elementAt(j);
                for (int k = j+1; k < loop; k++) {
                    BoxGroup bg2 = (BoxGroup)boxes.elementAt(k);
                    if (bg1.conflictWith(bg2)) {
                        continue;
                    } else {
                        BoxGroup newGroup = new BoxGroup(bg1, bg2);
                        boxes.addElement(newGroup);
                    }
                }
            }
        }
        int minArea = 0x7fffffff;
        int idx = 0;
        for (int i = boxes.size()-1; i > 0; i--) {
            BoxGroup bg = (BoxGroup)boxes.elementAt(i);
            if (bg.indices.size() < boxesData.length) {
                break;
            }
            //System.out.println("Area="+bg.area());
            if (bg.area() < minArea) {
                minArea = bg.area();
                idx = i;
            }
        }
        System.out.println("The best combination is "+idx);
        setLayout(new BorderLayout());
        BoxGroup theGroup = (BoxGroup)boxes.elementAt(idx);
        System.out.println(theGroup.toString(0));
        Canvas canv = new MyCanvas(theGroup);
        add(canv, BorderLayout.CENTER);
        setSize(640, 480);
        addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        });
    }

    public static void main(String[] args) {
        TestAlgo frame = new TestAlgo();
        frame.setVisible(true);
    }

    public static class MyCanvas extends Canvas {

        BoxGroup boxGroup = null;

        public MyCanvas(BoxGroup bg) {
            boxGroup = bg;
        }

        public void paint(Graphics g) {
            drawBoxGroup(g, 0, 0, boxGroup);
        }

        public static void drawBoxGroup(Graphics g, int x, int y, BoxGroup bg) {
            if (bg.gl == null && bg.gr == null) {
                System.out.println("Draw: x="+x+" y="+y+" w="+bg.width+" h="+bg.height);
                g.drawRect(x, y, bg.width, bg.height);
            } else {
                drawBoxGroup(g, x, y, bg.gl);
                if (bg.layout == bg.HOR) {
                    drawBoxGroup(g, x+bg.gl.width, y, bg.gr);
                } else {
                    drawBoxGroup(g, x, y+bg.gl.height, bg.gr);
                }
            }
        }
    }

    public static class BoxGroup {
        public static int HOR = 1;
        public static int VER = 2;
        public Vector indices = new Vector();
        public int width;
        public int height;
        public BoxGroup gl = null;
        public BoxGroup gr = null;
        public int layout = HOR;


        public BoxGroup(int index, int w, int h) {
            indices.add(new Integer(index));
            width = w;
            height = h;
        }

        public String toString() {
            StringBuffer buf = new StringBuffer();
            if (gl == null) {
                buf.append("Box index="+indices.elementAt(0)+" width="+width+" height="+height);
            } else {
                buf.append("Group layout="+(layout==HOR?"HOR":"VER")+" width="+width+" height="+height);
            }
            return buf.toString();
        }

        public String toString(int indent) {
            StringBuffer buf = new StringBuffer();
            for (int i = 0; i < indent; i++) {
                buf.append("  ");
            }
            buf.append(toString()+"\n");
            if (gl != null) {
                buf.append(gl.toString(indent+1));
                buf.append(gr.toString(indent+1));
            }
            return buf.toString();
        }

        public BoxGroup(BoxGroup g1, BoxGroup g2) {
            gl = g1;
            gr = g2;
            indices.addAll(g1.indices);
            indices.addAll(g2.indices);
            int area1 = (g1.width+g2.width)*Math.max(g1.height, g2.height);
            int area2 = Math.max(g1.width, g2.width)*(g1.height+g2.height);
            if (area1 <= area2) {
                width = g1.width+g2.width;
                height = Math.max(g1.height, g2.height);
                layout = HOR;
            } else {
                width = Math.max(g1.width, g2.width);
                height = g1.height+g2.height;
                layout = VER;
            }
        }

        public boolean conflictWith(BoxGroup g) {
            for (int i = 0; i < indices.size(); i++) {
                if (g.indices.contains(indices.elementAt(i))) {
                    return true;
                }
            }
            return false;
        }

        public int area() {
            return width*height;
        }
    }

}

调试易

挑战你的大脑！！一道有些难度的图形问题！

解决方案 »