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

初始问题是这样的！绳子问题，绳子初始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？怎么剪？
  public int line(int A,int B, int C,int N){
        int Na= 0;//A的最少个数；
        ......
        return Na;
}
直接答第三问，就可以了！

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

楼主的问题，第三问看的不是很明白，第三问a,b,c都为变量是什么意思，如果都是可变的，那还怎么求用最少a剪出b，c。都不确定啊，不太理解，望指导
这要分情况：根据公式：7B+5C<=15A
1、当要的B和C数量相同的情况下，即B=C=N,则 Na=Math.floor(4*N/5）+1
2、b c不同，但c能被3整除的情况Na=c/3+b%2+Math.floor(b/2）
3、b c不同，且c不能被3整除
    Na=？还要考虑下
算法如下：
不妨设A>B>=C，需要m个B,n个C，求需要多少个A？
每次仅取一个A，优先截取B，当剩余绳长R>=B且m>0，继续截取B，直到R<B或m=0；若此时R>=C且n>0，则截取C，直到R<C或n=0；此时，R为废绳。
若未完成要求，则再取一个A。直到完成为止。
       public int line(int A, int B, int C, int N) {
int Na = 0;// A的最少个数；
Na += A/2+C/3;
if(B%2==0){
Na+=C%3==0?0:1;
}else{
Na++;
Na+=(C%3-1>0)?1:0;
}
return Na;
}
一定要相信我们的cpu是足够快的
求最优解问题,有点难度!
题目的意思应该是这样的:三根绳子满足这样要求 A>B,C 值是任意的正整数,现在想B和C各N根,该怎么剪使需求的A的个数最小
如果要6个B,和6个C 最少用多少个A！怎么剪？
是最少有啊，还是最少用
LZ 可以去看看这个帖子：
http://topic.csdn.net/u/20090226/21/2158a637-1ca2-4eb8-a980-5328a076835b.html情况比较类似，比你这个稍微复杂，这个帖子当时加分到200分甚至后来现金求解答，也不知道还有没有结果，里面有不少大大的思想应该可以参考下
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的总数目
}}
方法getNUM（）得到截取B(B>=C)所需A
getNUM2()得到C所需A
刚测试了下，好像还可以。。没优化，欢迎拍砖。。
写了一个，用问题1验证的话没什么问题。大家有兴趣的话可以检验一下。
想法就是每次截取都保证剩余的绳子长度最小。这样最终截取的结果应该是
最节省材料的主要逻辑/**
* 最节省材料算法
* @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;
    }}
测试代码用问题1代入的            //绳子截取测试问1的情况
            int baseLength = 15;//绳子标准长度
            int lenA = 15;      //A绳子长度
            int cntA = 0;       //所需A绳子数量
            int lenB = 7;       //B绳子长度
            int cntB = 6;       //所需B绳子数量
            int lenC = 5;       //C绳子长度
            int cntC = 6;       //所需C绳子数量            CaculateBestCutting cutLines = new CaculateBestCutting(baseLength);
            int cntBase = cutLines.getMinLinesCount(lenA, cntA, lenB, cntB, lenC, cntC);
            System.out.println("所需标准绳子条数＝" + cntBase);
出力的日志
绳子截取开始
绳子A：长度＝15 数量＝0
绳子B：长度＝7 数量＝6
绳子C：长度＝5 数量＝6
取标准绳子绳子番号＝1
截取B绳剩余长度＝8
截取B绳剩余长度＝1
取标准绳子绳子番号＝2
截取B绳剩余长度＝8
截取B绳剩余长度＝1
取标准绳子绳子番号＝3
截取B绳剩余长度＝8
截取B绳剩余长度＝1
取标准绳子绳子番号＝4
截取C绳剩余长度＝10
截取C绳剩余长度＝5
截取C绳剩余长度＝0
取标准绳子绳子番号＝5
截取C绳剩余长度＝10
截取C绳剩余长度＝5
截取C绳剩余长度＝0
绳子截取完成
所需标准绳子条数＝5 边角料长度＝3
所需标准绳子条数＝5
更正错误                default:
                    //剩余长度不够截取
                    ⋯⋯
                    currentLineLen = 15;
                    ⋯⋯
                    break;
更正                default:
                    //剩余长度不够截取
                    ⋯⋯
                    currentLineLen = _baseLength;
                    ⋯⋯
                    break;
public static int line(int a, int b, int c, int n){
int nab = 0;//得到n个B 所需的A 的个数
int nac = 0;//得到n个C 所需的A 的个数
nab = n / (a / b) + n % (a / b);
if (a % b >= c){//直接用剪成B后剩余的绳子得到C
return nab;
} else {
nac = n / (a / c) + n % (a / c);
return nab + nac;
}
}
满足例子中的数据，15，7，5，6.其他的没测。不知道其他情况满足不满足。
修正： 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;
}
一个地方写错了，我把n当作定值6啦  哈哈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) < n) {//如果剩余的绳子剪不够N个C，则领取A剪C
int nc = n - nab * (a % b / c);
if (nc >= (a / c)){
nac = nc / (a / c) + nc % (a / c);
} else {
nac = 1;
}
}
} else {
nac = n / (a / c) + n % (a / c);
}
na = nab + nac;
System.out.println("需要"+ na +"个A，剩余角料：" + (na * a - n * (b + c)));
return  na;
}
我也验证了一下我的这个，结果正确了。
我的想法是每次截取都保证剩余的长度最短。
我只是个人认为这样截就最省材料了，不敢确认。
你再试试其它方法，最好把想法写出来别光写代码。绳子截取开始
绳子A：长度＝9 数量＝0
绳子B：长度＝6 数量＝3
绳子C：长度＝3 数量＝3
取标准绳子绳子番号＝1
截取B绳剩余长度＝3
截取C绳剩余长度＝0
取标准绳子绳子番号＝2
截取B绳剩余长度＝3
截取C绳剩余长度＝0
取标准绳子绳子番号＝3
截取B绳剩余长度＝3
截取C绳剩余长度＝0
绳子截取完成
所需标准绳子条数＝3 边角料长度＝0
所需标准绳子条数＝3
嗯，我的想法是先剪取B绳，看剩余绳子是否可以剪C绳。如果够剪直接用剩余绳子剪，如果不够则再另取标准绳子剪C绳了。
也不确定这种方式是不是最节省材料的。