'Most efficient allocation of materials ordered'算法：-Java 学习之路

最有效的材料分配有序java编程问题：

这是一个我根本无法处理的编程问题 . 这是一个面试问题所以需要在10-15分钟内解决 .

一家公司希望将三种尺寸电路板的木材订购自动化为最具成本效益的订单（较长的电路板较便宜） . 木材公司提供的木材以16'，12'和8'板销售 . 板越长，越便宜 . 订单是7'，6'和5'板的倍数单位 . 所以你可以从一个16'一个或三个5'（16个中）中获得两个7'板，等等 . 如果你只需要两个5'板，你可以订购一个12'，而不是16' . 编写一个算法，该算法将接受三种类型的混合板数量的订单，并返回三种可用尺寸中最高效（成本效益）的订单 .

我不禁想到改变最佳造币的问题，但与此相比，这相对简单 . 似乎有项目频率的元素，但我看不出如何分配最佳顺序 .

我认为这是一个两步过程，第一步是将频率记录在 Map 中，例如6 x 7页脚，5 x 6页脚等 . 频率图按值排序，这就是我卡住的地方 .

只是为了澄清：更大的电路板更便宜，应尽可能先使用 .

我会继续看这个，但如果有人有想法，我将不胜感激 .

1 回答

package max.test.com;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/*
 * Board Cutter algorithm based on John T Erickson's 
 * code found at http://pastebin.com/1XPiBD20
 * 
 * I can't take credit for it - I just rendered it to Java  
 * 
 * Max Tomlinson
 * 
 */
public class BoardCutter
{

    static List<Double> boards;
    static List<Double> lengthsNeeded;

    static double cutWidth = Double.NaN;
    static double totalBoardLength;

    static int lengthsNeededLeft = 0;

    static List<String> instructions = new ArrayList<String>();
    static List<String> summary = new ArrayList<String>();

    public static void main(String[] args)
    {
        double[] tmp = new double[] { 48, 48, 48, 48, 48, 48 };
        boards = new ArrayList<Double>();
        for (int i = 0; i < tmp.length; i++)
        {
            boards.add(tmp[i]);
            totalBoardLength += tmp[i];
        }

        lengthsNeeded = new ArrayList<Double>();

        tmp = new double[] { 36.75, 36.5, 36.5, 26.25, 26.125, 22.5, 21, 20.5,
                14.5, 9.25, 9, 6.5, 4 };

        for (int i = 0; i < tmp.length; i++)
        {
            lengthsNeeded.add(tmp[i]);
        }

        cutWidth = 0.125;

        Collections.sort(lengthsNeeded);
        Collections.reverse(lengthsNeeded); //sorted high to low - biggest cuts first

        lengthsNeededLeft = lengthsNeeded.size();

        writeLine("Boards: ");

        double boardSum = 0;

        Iterator<Double> itd = boards.iterator();
        while (itd.hasNext())
        {
            double board = itd.next();
            writeLine("" + board);
            boardSum += board;
        }

        writeLine("Total: " + boardSum);

        writeLine("Lengths Needed:");

        double lengthsNeededSum = 0;

        itd = lengthsNeeded.iterator();

        while (itd.hasNext())
        {
            double ln = itd.next();
            writeLine("" + ln);
            lengthsNeededSum += ln;
        }

        writeLine("Total: " + lengthsNeededSum);

        tryCut();

        Collections.reverse(instructions);

        for (int i = 0; i < instructions.size(); i++)
            writeLine("Cut " + (i + 1) + ": " + instructions.get(i));

        for (int i = 0; i < summary.size(); i++)
            writeLine(summary.get(i));
    }

    /*
     * recursive cutting method
     */
    static boolean tryCut()
    {
        //last case, then exit
        if (lengthsNeededLeft == 0)
        {
            double boardLengthRemaining = 0;

            Iterator<Double> it = boards.iterator();
            while (it.hasNext())
            { // sum
                double board = it.next();
                if (!Double.isNaN(board)) 
                    boardLengthRemaining += board;                  
            }

            summary.add("Boards Remaining: ");

            for (int j = 0; j < boards.size(); j++)
            {
                if (boards.get(j).equals(Double.NaN)) continue;
                summary.add(" Board " + j + ": " + boards.get(j));
            }

            summary.add("Total Remaining " + boardLengthRemaining
                    + " efficiency "
                    + (100 * (1 - (boardLengthRemaining) / totalBoardLength)));

            return true;
        }

        //normal, recursive case

        //loop for all lengths needed
        for (int i = 0; i < lengthsNeeded.size(); i++)
        {
            double lengthNeeded = lengthsNeeded.get(i);

            if (Double.isNaN(lengthNeeded)) continue; //isNaN = 'done'

            for (int j = 0; j < boards.size(); j++)
            {
                double board = boards.get(j);

                if ( Double.isNaN(board)) continue; //isNaN = 'in use'

                double boardRemaining = board - lengthNeeded - cutWidth;

                if (boardRemaining >= 0.0)
                {
                    lengthsNeeded.set(i, Double.NaN); //set this length needed to 'done'
                    lengthsNeededLeft--;

                    boards.set(j, Double.NaN); //set board to used

                    boards.add(0, boardRemaining); //add new cut board remainder to front of available boards for possible reuse

                    int newBoardIndex = boards.size() - 1; //adjust size

                    //recursive call
                    if (tryCut())
                    {
                        instructions.add("Cut board " + (j + 1) + " of length " + board 
                                + " to size: " + lengthNeeded 
                                + " (leaving board " +  (newBoardIndex + 1) + " of length "
                                +  boardRemaining + ")");
                        return true;                        
                    }

                    boards.remove(boards.size() - 1);

                    lengthsNeeded.set(i, lengthNeeded);
                    lengthsNeededLeft++;

                    boards.set(j, board);
                }
            }
        }

        // all boards are too short 

        return false;
    }

    static void writeLine(String s)
    {
        System.out.println(s);
    }
}
//output
/*
Boards: 
48.0
48.0
48.0
48.0
48.0
48.0
Total: 288.0
Lengths Needed:
36.75
36.5
36.5
26.25
26.125
22.5
21.0
20.5
14.5
9.25
9.0
6.5
4.0
Total: 269.375
Cut 1: Cut board 1 of length 48.0 to size: 36.75 (leaving board 7 of length 11.125)
Cut 2: Cut board 2 of length 48.0 to size: 36.5 (leaving board 8 of length 11.375)
Cut 3: Cut board 3 of length 48.0 to size: 36.5 (leaving board 9 of length 11.375)
Cut 4: Cut board 4 of length 48.0 to size: 26.25 (leaving board 10 of length 21.625)
Cut 5: Cut board 5 of length 48.0 to size: 26.125 (leaving board 11 of length 21.75)
Cut 6: Cut board 6 of length 48.0 to size: 22.5 (leaving board 12 of length 25.375)
Cut 7: Cut board 10 of length 21.625 to size: 21.0 (leaving board 13 of length 0.5)
Cut 8: Cut board 11 of length 21.75 to size: 20.5 (leaving board 14 of length 1.125)
Cut 9: Cut board 12 of length 25.375 to size: 14.5 (leaving board 15 of length 10.75)
Cut 10: Cut board 7 of length 11.125 to size: 9.25 (leaving board 16 of length 1.75)
Cut 11: Cut board 8 of length 11.375 to size: 9.0 (leaving board 17 of length 2.25)
Cut 12: Cut board 9 of length 11.375 to size: 6.5 (leaving board 18 of length 4.75)
Cut 13: Cut board 15 of length 10.75 to size: 4.0 (leaving board 19 of length 6.625)
Boards Remaining: 
 Board 12: 0.5
 Board 13: 1.125
 Board 15: 1.75
 Board 16: 2.25
 Board 17: 4.75
 Board 18: 6.625
Total Remaining 17.0 efficiency 94.09722222222221
*/

回复于 2024-04-25T06:18:13+08:00

'Most efficient allocation of materials ordered'算法：

1 回答

相关问题