求一非递归算法！非递归！

Question

      在实际生活中遇到一些问题，现在简单描述一下，希望大家有什么好的算法告诉我，有源码更好。问题描述：      前提：原材可以无限制取，但最终余材要最少。      详细描述：开始只有原材，余材为零。原材可能有多种，按照某种情况截取，第一次截取后如果余材不为0则归类为余材，下次截取时先在余材中寻找符合条件的，有则继续在余材中寻找下一个符合条件的，反之在原材中寻找。例1：
   原材长度:3m，7m，9m（各有无限根）
   余材长度：0m
   截取情况：4根2m的
   获得结果：取9m的1根余1m，余材1m例2：
   原材长度:3m，8m，9m
   余材长度：0m
   截取情况：4根2m的
   获得结果：取8m的1根余0m，余材0m例3：
   原材长度:3m，7m
   余材长度：0m
   截取情况：4根2m的
   获得结果：取3m的1根余1m，取7m的一根余1,m，余材1m，1m，总共2m例4：
   原材长度:3m，7m
   余材长度：0m
   截取情况：1根2m的
   获得结果：取3m的1根余1m，余材1m例5：
   原材长度:3m，7m,9m
   余材长度：0m
   截取情况：2根3m的，4根2m的
   获得结果：取3m的2根余0m，取9m的一根余1m，总共余材1m例5：
   原材长度:4m，7m,9m
   余材长度：0m
   截取情况：2根3m的，4根2m的
   获得结果：取1根7m的余1根1m，取1根9m的余1m，总共余2m

Answer 1

有点意思，先Mark一下，
这个的最优为啥不是2个7m（=2+2+3）的，最后余0呢？

Answer 2

例1：
   原材长度:3m，7m，9m（各有无限根）
   余材长度：0m
   截取情况：4根2m的
   获得结果：取9m的1根余1m，余材1m
截取的情况 
2 + 2 + 2 + 2  
6 + 2
8第一种情况  取4个 3M的    余 1M * 4 
第二种情况  取1个 7M的   余 1M,  取1个 3M 的 余1M;
第三种情况  取1个 9M的  余 1M

Answer 3

例5：
   原材长度:3m，7m,9m
   余材长度：0m
   截取情况：2根3m的，4根2m的
   获得结果：取3m的2根余0m，取9m的一根余1m，总共余材1m
截取的情况
3 + 3 + 2 + 2 + 2+ 2  //拼3
7 + 7                 //拼7
9 + 5                 //拼9第一种情况 取6个 3M 的 余 1M*4
第二种情况 取2个 7M 的 刚好用完
第三种情况 取1个 9M 的 刚好用完  取一个7M 的 余2M

Answer 4

例5：
   原材长度:3m，7m,9m
   余材长度：0m
   截取情况：2根3m的，4根2m的
   获得结果：取3m的2根余0m，取9m的一根余1m，总共余材1m例6：
   原材长度:4m，7m,9m
   余材长度：0m
   截取情况：2根3m的，4根2m的
   获得结果：取1根7m的余1根1m，取1根9m的余1m，总共余2m
确实，这两个举例是错误的。例5：
原材长度:3m，7m,9m
余材长度：0m
截取情况：2根3m的，4根2m的
获得结果：取7m的2根余0m

Answer 5

    这是之前的算法，用的是深度搜索，实际中可能会存在一些问题，想用非递归取实现，暂时没有想到合适的优化方案。procedure DFS(ABarIndex, ABarCount: Integer);
  var
    I, nUnusedLen: Integer;
  begin
    //剪枝
    if (nHaveWasted > nMinWaste) or ((nLenCanUsed - nAllBarLen) > nMinWaste) then
      Exit;
    Inc(nTerminationCount);
    if (ABarIndex = 0) and (ABarCount = -1) then //找到一个方案
    begin
      nMinWaste := nLenCanUsed;              //更新找到的更小的消耗
      SetLength(oBestAns, Length(oFindAns));
      for I := Low(oFindAns) to High(oFindAns) do
        oBestAns[I] := oFindAns[I];
      oBestSurplusList := oSaveSurplusList;  //记录最好方案时剩下的料头
      Exit;
    end;
    if nTerminationCount >= 100000 then
      Exit;  //达到一定搜索次数就退出，避免数据量过大时死机
    if (ABarIndex > 0) and (ABarCount = -1) then
    begin
      Dec(ABarIndex);
      ABarCount := ABarList[ABarIndex].Count - 1;
      DFS(ABarIndex, ABarCount);
      Exit;
    end;
    //先从已经分配的料中里面搜索
    for I := Low(oFindAns) to High(oFindAns) do
    if oFindAns[I].UnUsedlen >= ABarList[ABarIndex].Len then
    begin
      oBarList := oFindAns[I].BarList;
      SetLength(oBarList, Length(oBarList) + 1);
      oBarList[High(oBarList)] := ABarList[ABarIndex];
      oBarList[High(oBarList)].Count := 1;
      oFindAns[I].BarList := oBarList;      nLenCanUsed := nLenCanUsed - ABarList[ABarIndex].Len;
      nAllBarLen := nAllBarLen - ABarList[ABarIndex].Len;
      nUnusedLen := oFindAns[I].UnUsedlen;
      if nUnusedLen < nMinBarLen then
        nHaveWasted := nHaveWasted + nUnusedLen; //更新已经确定消耗了的      DFS(ABarIndex, ABarCount - 1);
      //恢复原样
      if nUnusedLen < nMinBarLen then
        nHaveWasted := nHaveWasted - nUnusedLen;
      nAllBarLen := nAllBarLen + ABarList[ABarIndex].Len;
      nLenCanUsed := nLenCanUsed + ABarList[ABarIndex].Len;
      oBarList := oFindAns[I].BarList;
      SetLength(oBarList, High(oBarList));
      oFindAns[I].BarList := oBarList;
    end;
    //从原材里面搜索
    for I := Low(oSaveSurplusList) to High(oSaveSurplusList) do
    if (oSaveSurplusList[I].Count <> 0) and (oSaveSurplusList[I].Len >= ABarList[ABarIndex].Len) then
    begin
      Dec(oSaveSurplusList[I].Count);
      SetLength(oBarList, 1);
      oBarList[0] := ABarList[ABarIndex];
      oBarList[0].Count := 1;
      if oSaveSurplusList[I].Count >= 0 then
        sRe := SSurplus
      else
        sRe := SMaterials;
      SetLength(oFindAns, Length(oFindAns) + 1);
      oFindAns[High(oFindAns)] := DetailsData(Length(oFindAns), 1, oSaveSurplusList[I].Len,
        ABarList[ABarIndex].BarFormat, oBarList, sRe);      nUnusedLen := oFindAns[High(oFindAns)].UnUsedlen;
      nLenCanUsed := nLenCanUsed + nUnusedLen;
      nAllBarLen := nAllBarLen - ABarlist[ABarIndex].Len;
      if nUnusedLen < nMinBarLen then
        nHaveWasted := nHaveWasted + nUnusedLen;
      DFS(ABarIndex, ABarCount - 1);      //恢复数据
      if nUnusedLen < nMinBarLen then
        nHaveWasted := nHaveWasted - nUnusedLen;
      nAllBarLen := nAllBarLen + ABarlist[ABarIndex].Len;
      nLenCanUsed := nLenCanUsed - nUnusedLen;
      SetLength(oFindAns, High(oFindAns));
      Inc(oSaveSurplusList[I].Count);
    end;
  end;    谁有好的想法，帮忙优化一下，小弟在此先谢谢各位啦~

Answer 6

我觉得人工配置未必不是一个办法啊,如果实际生产中用料情况有限的话,把预先的数据全部放入数据库中,无法匹配的时候使用人工输入,使用一段时间后,基本上没有找不到的case了