一个算法有关问题，最省材料的算法

一个算法问题，最省材料的算法！
初始问题是这样的！绳子问题，绳子初始15m，断的绳子不能再接。B,C<A
A：15m
B：7m
C：5m
问1，如果要6个B,和6个C 最少用多少个A！怎么剪？
答1：剪发1：2*7+1=15 剪发2：3*5=15 最少要 剪发1*3+剪发2*2，共5个A，剩余3个1m的废绳。
问2，如果，要N个B，N个C，最少用多少个A，怎么剪？
问3，如果，当ABC 问变量时，怎么求最少要多少个A？怎么剪？

Java code

  public int line(int A,int B, int C,int N){        int Na= 0;//A的最少个数；        ......        return Na;}

直接答第三问，就可以了！

[解决办法]
package caculate;

public class test {

private int A;
private int B;
private int C;
private int Nb;//B的数目
private int Nc;//C的数目

private int temp;

/**
* 该方法得到截取B、C中较长者所需A的数。
*/
public int getNUM(int m, int n,int N){
if(N<=0)return 0;
int k1=m/n;
if(k1==0){return 1;}
temp=N%k1;
if(temp==0)return N/k1;
return N/k1+1;//
}


public int getNUM2(int m, int n){
int k1;
if(temp==0){k1=0;}
else
k1=(A-temp*B)/C;
int k2=(A%B/C)*(Nb/(A/B));
return getNUM(A,C,Nc-k1-k2);
}
public int getBig(){
if(B>=C){
return B;}
return C;
}
public int getSmall(){
if(B<C){
return B;}
return C;
}
public static void main(String[] args) {
test t=new test();
t.A=15;
t.B=8;
t.C=8;
t.Nb=6;
t.Nc=6;
System.out.println(t.getNUM(t.A, t.getBig(), t.Nb));//截取B（设B>=C）所需A数目
System.out.println(t.getNUM2(t.A, t.getSmall()));//所需A的总数目


}

}

[解决办法]
写了一个，用问题1验证的话没什么问题。大家有兴趣的话可以检验一下。
想法就是每次截取都保证剩余的绳子长度最小。这样最终截取的结果应该是
最节省材料的

主要逻辑

Java code

/** * 最节省材料算法 * @deprecated 最短剩余确保法则 * @author oushuuryuu */class CaculateBestCutting {    private int _baseLength; //标准绳子长度    /**     * 构造函数     * @param baseLength 标准绳子长度     */    public CaculateBestCutting(int baseLength) {        this._baseLength = baseLength;    }    /**     * 所需最少根数取得     * @param lenA A绳的长度     * @param cntA A绳的数量     * @param lenB B绳的长度     * @param cntB B绳的数量     * @param lenC C绳的长度     * @param cntC C绳的数量     * @return     */    public int getMinLinesCount(int lenA, int cntA,int lenB,int cntB,int lenC,int cntC) {        int minCount = 0;       //所需要标准绳子的长度        int currentLineLen = 0; //当前绳子的长度        int totalWastedLen = 0; //剩余绳子长度        System.out.println("绳子截取开始");        System.out.println("绳子A：长度＝" + lenA + " " + "数量＝" + cntA);        System.out.println("绳子B：长度＝" + lenB + " " + "数量＝" + cntB);        System.out.println("绳子C：长度＝" + lenC + " " + "数量＝" + cntC);        //到绳子全部截取完为止做下面的处理        while (cntA + cntB + cntC > 0) {            int paramLenA = cntA>0?lenA:_baseLength + 1;            int paramLenB = cntB>0?lenB:_baseLength + 1;            int paramLenC = cntC>0?lenC:_baseLength + 1;            int cutIndex = getCuttingIndex(currentLineLen, paramLenA, paramLenB, paramLenC);            switch (cutIndex) {                case 0:                    //截取绳子A                    currentLineLen -= lenA;                    cntA--;                    System.out.println("截取A绳 剩余长度＝" + currentLineLen);                    break;                case 1:                    //截取绳子B                    currentLineLen -= lenB;                    cntB--;                    System.out.println("截取B绳 剩余长度＝" + currentLineLen);                    break;                case 2:                    //截取绳子C                    currentLineLen -= lenC;                    cntC--;                    System.out.println("截取C绳 剩余长度＝" + currentLineLen);                    break;                default:                    //剩余长度不够截取                    totalWastedLen += currentLineLen;                    currentLineLen = 15;                    minCount++;                    System.out.println("取标准绳子 绳子番号＝" + minCount);                    break;                                }        }        System.out.println("绳子截取完成");        System.out.println("所需标准绳子条数＝" + minCount + " " + "边角料长度＝" + totalWastedLen);        return minCount;    }    /**     * 取得应该截取的绳子     * @param currentLen 剩余绳子的长度     * @param lenA       A绳的长度     * @param lenB       B绳的长度     * @param lenC       C绳的长度     * @return -1：截取不可 0：截取A绳 1：截取B绳 2：截取C绳     */    private int getCuttingIndex(int currentLen, int lenA, int lenB, int lenC) {        int index = -1;        //绳子长度由小到大排序        TreeMap<Integer,Integer> sortMap = new TreeMap<Integer,Integer>();        sortMap.put(lenA, 0);        sortMap.put(lenB, 1);        sortMap.put(lenC, 2);        if (sortMap.containsKey(currentLen)) {            index = sortMap.get(currentLen);        } else {            //比currentLen小的最大键值的map取得            Entry<Integer,Integer> targetMap = sortMap.lowerEntry(currentLen);            if (targetMap != null) {                index = targetMap.getValue();            }        }        return index;    }} 
 
[解决办法]
修正：
Java code
    public static int line(int a, int b, int c, int n){        System.out.println();        System.out.println("开始剪绳子......");        System.out.println("绳子A：" + a);        System.out.println("绳子B：" + b);        System.out.println("绳子C：" + c);        System.out.println("得到B、C的个数：" + n);                int nab = 0;//得到n个B 所需的A 的个数        int nac = 0;//得到n个C 所需的A 的个数        int na = 0;//一共需要的A 的个数                nab = n / (a / b) + n % (a / b);        if (a % b >= c){//直接用剪成B后剩余的绳子得到C            if (nab * (a % b / c) < 6) {//如果剩余的绳子剪不够N个C，则领取A剪C                int nc = 6 - nab * (a % b / c);                nac = nc / (a / c) + nc % (a / c);            }        } else {            nac = n / (a / c) + n % (a / c);        }        na = nab + nac;        System.out.println("需要"+ na +"个A，剩余角料：" + (na * a - n * (b + c)));        return  na;    } 

 

查看更多 下一篇