蛇吞食物问题 动态规划 矩形切割问题

mythmgn

蛇肚子的大小是100*100    食物的大小不一定比如10*40，32*84；

现在输入一系列食物，要求用尽可能少的蛇吞并食物，并且这个算法要足够快。
输入食物的信息放在文件food.txt中，格式
50 //100个食物
20 50 //食物的规格 x y
70 80
...


现在求解用多少条蛇吞并这些食物.    一条蛇可以吞并多个食物,但是食物加起来不能超过这个100*100的规格


输出结果1.用的蛇的数目,和这个算法用的时间。
        2.蛇内食物组合    如  2 0 0 50 50 60 60 100 100   
          这个意思是 2个食物,第一个食物左上坐标为 (0,0)(右下为50,50)  第二个食物左上为60,60 右下为100 100    食物规格分别为50 50  40 40
          有多少条蛇得输出多少行这样的序列


------------------------------
感觉像是个切割的 动态规划问题 我算法不好，请大家帮忙想想
------------------------------
先将食物全部读入内存后，我的想法：
      先将食物做排序处理，长X和宽Y 没有区分，谁做长和宽都可以。按照先大后小的排序（
      优先组合尽可能大的蛇，就是先大后小的，有人说这样的组合算法快。但是不是最优。
--------------------------------------------------------------------

大家给下思路 谢谢了

emacsnw

bin packing 问题，NP难，一般用贪心等近似算法求解。