有一批钢材，长度为3000mm。需要将它们切割成长度不一的零件，问如何切割
才能使用料最少。
输入
第一行表示零件的种类n，之后是n行。
每一行包含两个数字 l ， m,    l表示零件的长度，m表示需要的这种零件的个数
其中  m < 100，

输出，输出总共需要的钢材的数量

sample 

3
1500 3
1000 4
2000 2

输出 6

[另] 如果还需要考虑钢材切割方式最少的方式，那怎么办？
比如以上的采用的切割方式有
1500 * 2
2000 + 1000
1000 * 3

• 如果先不考虑下面的条件怎么做？要搜吗？哪位给点思路，谢谢了 ：） (324) queyue2004 2005-08-08 20:53:10
  • 高中的线型规划把，列个方程先，高考过的一定会 (0) sunmoonstar_love 2005-08-08 20:56:45
• 硬币题，DP吧 (324) sunmoonstar_love 2005-08-08 20:58:01
  • 能不能说具体点，谢谢：） (0) queyue2004 2005-08-08 21:05:16
    • 不好意思没有好的想法呢 (0) sunmoonstar_love 2005-08-08 21:06:34
      • Re:不好意思没有好的想法呢 (0) queyue2004 2005-08-08 21:22:16
• 把小棍子从大到小排序，然后先组第一个3000，再组第二个3000，每次从前往后遍历一遍。 (324) tengshengbo 2005-08-08 21:40:33
  • 如果加上附加条件，只需让钢材尽可能多的正好分割（ (0) tengshengbo 2005-08-08 21:43:59
    • 如果加上附加条件，只需让钢材尽可能多的正好分割（没有废料）。可能必须得搜。 (0) tengshengbo 2005-08-08 21:45:17
      • 对不起，我可能没理解你的意思，请看里面这个例子[见内] (167) queyue2004 2005-08-08 22:02:57