求一思路和算法

Question

不知道这个发在哪个区好了，看这里人气不错，就来了
问题如下：
工厂每天要把多个固定大小的长方形的模板（原料）切割成若干种不同长宽的方形的待加工品，
当然每种待加工品也有数量上的计划，我想计算怎么切割才是最省料的切法
注：1.每切一刀必须是一直到头的，（这个是和工厂的机器有关的）
    2.待加工品暂不考虑有其他形状的可能，只有长方形，正方形我的想法是，比如每天计划切8种材料，每种需要的个数不同，是不是要先切大的，然后看看剩的料切多少小的，
这其中要考虑这8种的面积，长宽，还有数量。期待牛人的算法。

Answer 1

import java.util.HashMap;
import java.util.Map;
import java.util.Iterator;/**
 * Author: s1314bin
 * Date  : 2010-2-5
 * Time  : 9:24:00
 * Comment:
 */
public class test {
    public static void main(String[] args){
        machine machine=new machine();
        shape material=new shape(50,100);
        shape product1=new shape(20,30);
        machine.work(material,product1,5);
        if(!machine.leave.isEmpty()){
            System.out.println("Result is right================");
            Iterator iter=machine.leave.entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry e = (Map.Entry) iter.next();
                shape shape=(shape)e.getKey();
                System.out.println("宽："+shape.getWidth()+"长："+shape.getLenth()+"数量："+e.getValue());
            }
        }
        shape product2=new shape(20,20);
        machine.work(material,product2,5);
        if(machine.leave.isEmpty())
            System.out.println("Result is right");
    }
}class machine {
    Map leave=new HashMap();
    public void work(shape material,shape  product,int num){
        int sum=0,count=0;
        sum=useleave(product);
        while((sum+count)<num){
            count=process(material,product);
            sum+=count;
        }
        incise(material,product,(num-sum));
    }    //  材料切割
    int process(shape material,shape product){
        int a=0,b=0;
        int width=0,lenth=0;
        int l1=0,l2=0;
        if (material.getWidth() > product.getLenth()) {
            a=material.getWidth()/product.getLenth();
            b=material.getLenth()/product.getWidth();
            width=material.getWidth()%product.getLenth();
            if(width!=0){
                l1=exist(new shape(width,product.getWidth()));
                leave.put(new shape(width,product.getWidth()),new Integer(b+l1));
            }
            lenth=material.getLenth()%product.getWidth();
            if(lenth!=0){
                l2=exist(new shape(lenth,material.getWidth()));
                leave.put(new shape(lenth,material.getWidth()),new Integer(1+l2));
            }
            return a*b;
        }
        else{
            a=material.getWidth()/product.getWidth();
            b=material.getLenth()/product.getLenth();
            width=material.getWidth()%product.getWidth();
            if(width!=0){
                l1=exist(new shape(width,material.getLenth()));
                leave.put(new shape(width,material.getLenth()),new Integer(1+l1));
            }
            lenth=material.getLenth()%product.getLenth();
            if(lenth!=0){
                l2=exist(new shape(lenth,product.getWidth()));
                leave.put(new shape(lenth,product.getWidth()),new Integer(a+l2));
            }
            return a*b;
        }
    }    // 切割指定数量的模板
    void incise(shape material,shape product,int num){
        if(num==0) return;
        int a=0,b=0;
        int width=0,lenth=0;
        int count=0,ll=0;
        int l1=0,l2=0,l3=0;
        if (material.getWidth() > product.getLenth()) {
            a=material.getWidth()/product.getLenth();
            count=num/a+1;
            ll=count*a-num;
            width=material.getWidth()%product.getLenth();
            lenth=material.getLenth()%product.getWidth();
            l1=exist(new shape(width,product.getWidth()));
            l2=exist(new shape(width+ll*product.getLenth(),product.getWidth()));
            l3=exist(new shape((material.getLenth()-count*product.getWidth()),material.getWidth()));
            leave.put(new shape(width,product.getWidth()),new Integer(count-1+l1));
            leave.put(new shape(width+ll*product.getLenth(),product.getWidth()),new Integer(1+l2));
            leave.put(new shape((material.getLenth()-count*product.getWidth()),material.getWidth()),new Integer(1+l3));
        }else{
            a=material.getWidth()/product.getWidth();
            count=num/a+1;
            ll=count*a-num;
            width=material.getWidth()%product.getWidth();
            lenth=material.getLenth()%product.getLenth();
            l1=exist(new shape(product.getWidth(),lenth));
            l2=exist(new shape(product.getWidth(),lenth+ll*product.getLenth()));
            l3=exist(new shape((material.getWidth()-count*product.getWidth()),material.getLenth()));
            leave.put(new shape(product.getWidth(),lenth),new Integer(count-1+l1));
            leave.put(new shape(product.getWidth(),lenth+ll*product.getLenth()),new Integer(1+l2));
            leave.put(new shape((material.getWidth()-count*product.getWidth()),material.getLenth()),new Integer(1+l3));
        }
    }    // 利用剩余材料 切割模板
    int useleave(shape product){
        if(leave.isEmpty())
            return 0;
        int sum=0;
        Iterator iter=leave.entrySet().iterator();
        while(iter.hasNext()){
            Map.Entry e = (Map.Entry)iter.next();
            if(isuse((shape)e.getKey(),product)){
                sum+=process((shape)e.getKey(),product)*Integer.parseInt(e.getValue().toString());
                leave.remove(e.getKey());
            }
        }
        return sum;
    }    //  判断剩余材料 是否能用
    boolean isuse(shape material,shape product){
        if (material.getWidth() >= product.getWidth()&&material.getLenth() >= product.getLenth())
            return true;
        return false;
    }    //  剩余材料里的数量
    int exist(shape shape){
        if(leave.containsKey(shape))
            return Integer.parseInt(leave.get(shape).toString());
        return 0;
    }
}
class shape{
    private int lenth;
    private int width;    shape(int lenth, int width) {
        if(width<lenth){
            this.lenth = lenth;
            this.width = width;
        }
        else{
            this.width = lenth;
            this.lenth = width;
        }
    }    public int getLenth() {
        return lenth;
    }    public int getWidth() {
        return width;
    }
//    public boolean equals(Object o) {
//        if (this == o) return true;
//        if (o == null || getClass() != o.getClass()) return false;
//
//        shape shape = (shape) o;
//
//        if (lenth != shape.lenth) return false;
//        if (width != shape.width) return false;
//
//        return true;
//    }
//
//    public int hashCode() {
//        int result = lenth;
//        result = 31 * result + width;
//        return result;
//    }
}实在是找不好的解决方案
你要求一刀是切断的我只是勉强实现功能,只供参考

Answer 2

晕倒 一次还贴不完  我分开发 test类我就不发了class shape{
    private int lenth;
    private int width;    shape(int lenth, int width) {
        if(width<lenth){
            this.lenth = lenth;
            this.width = width;
        }
        else{
            this.width = lenth;
            this.lenth = width;
        }
    }    public int getLenth() {
        return lenth;
    }    public int getWidth() {
        return width;
    }
//    public boolean equals(Object o) {
//        if (this == o) return true;
//        if (o == null || getClass() != o.getClass()) return false;
//
//        shape shape = (shape) o;
//
//        if (lenth != shape.lenth) return false;
//        if (width != shape.width) return false;
//
//        return true;
//    }
//
//    public int hashCode() {
//        int result = lenth;
//        result = 31 * result + width;
//        return result;
//    }
}

Answer 3

class machine {
    Map leave=new HashMap();
    public void work(shape material,shape  product,int num){
        int sum=0,count=0;
        sum=useleave(product);
        while((sum+count)<num){
            count=process(material,product);
            sum+=count;
        }
        incise(material,product,(num-sum));
    }    //  材料切割
    int process(shape material,shape product){
        int a=0,b=0;
        int width=0,lenth=0;
        int l1=0,l2=0;
        if (material.getWidth() > product.getLenth()) {
            a=material.getWidth()/product.getLenth();
            b=material.getLenth()/product.getWidth();
            width=material.getWidth()%product.getLenth();
            if(width!=0){
                l1=exist(new shape(width,product.getWidth()));
                leave.put(new shape(width,product.getWidth()),new Integer(b+l1));
            }
            lenth=material.getLenth()%product.getWidth();
            if(lenth!=0){
                l2=exist(new shape(lenth,material.getWidth()));
                leave.put(new shape(lenth,material.getWidth()),new Integer(1+l2));
            }
            return a*b;
        }
        else{
            a=material.getWidth()/product.getWidth();
            b=material.getLenth()/product.getLenth();
            width=material.getWidth()%product.getWidth();
            if(width!=0){
                l1=exist(new shape(width,material.getLenth()));
                leave.put(new shape(width,material.getLenth()),new Integer(1+l1));
            }
            lenth=material.getLenth()%product.getLenth();
            if(lenth!=0){
                l2=exist(new shape(lenth,product.getWidth()));
                leave.put(new shape(lenth,product.getWidth()),new Integer(a+l2));
            }
            return a*b;
        }
    }    // 切割指定数量的模板
    void incise(shape material,shape product,int num){
        if(num==0) return;
        int a=0,b=0;
        int width=0,lenth=0;
        int count=0,ll=0;
        int l1=0,l2=0,l3=0;
        if (material.getWidth() > product.getLenth()) {
            a=material.getWidth()/product.getLenth();
            count=num/a+1;
            ll=count*a-num;
            width=material.getWidth()%product.getLenth();
            lenth=material.getLenth()%product.getWidth();
            l1=exist(new shape(width,product.getWidth()));
            l2=exist(new shape(width+ll*product.getLenth(),product.getWidth()));
            l3=exist(new shape((material.getLenth()-count*product.getWidth()),material.getWidth()));
            leave.put(new shape(width,product.getWidth()),new Integer(count-1+l1));
            leave.put(new shape(width+ll*product.getLenth(),product.getWidth()),new Integer(1+l2));
            leave.put(new shape((material.getLenth()-count*product.getWidth()),material.getWidth()),new Integer(1+l3));
        }else{
            a=material.getWidth()/product.getWidth();
            count=num/a+1;
            ll=count*a-num;
            width=material.getWidth()%product.getWidth();
            lenth=material.getLenth()%product.getLenth();
            l1=exist(new shape(product.getWidth(),lenth));
            l2=exist(new shape(product.getWidth(),lenth+ll*product.getLenth()));
            l3=exist(new shape((material.getWidth()-count*product.getWidth()),material.getLenth()));
            leave.put(new shape(product.getWidth(),lenth),new Integer(count-1+l1));
            leave.put(new shape(product.getWidth(),lenth+ll*product.getLenth()),new Integer(1+l2));
            leave.put(new shape((material.getWidth()-count*product.getWidth()),material.getLenth()),new Integer(1+l3));
        }
    }    // 利用剩余材料 切割模板
    int useleave(shape product){
        if(leave.isEmpty())
            return 0;
        int sum=0;
        Iterator iter=leave.entrySet().iterator();
        while(iter.hasNext()){
            Map.Entry e = (Map.Entry)iter.next();
            if(isuse((shape)e.getKey(),product)){
                sum+=process((shape)e.getKey(),product)*Integer.parseInt(e.getValue().toString());
                leave.remove(e.getKey());
            }
        }
        return sum;
    }    //  判断剩余材料 是否能用
    boolean isuse(shape material,shape product){
        if (material.getWidth() >= product.getWidth()&&material.getLenth() >= product.getLenth())
            return true;
        return false;
    }    //  剩余材料里的数量
    int exist(shape shape){
        if(leave.containsKey(shape))
            return Integer.parseInt(leave.get(shape).toString());
        return 0;
    }
}