递归回溯求助！

Question

我有点为难了。我必须实现一个递归回溯算法，该算法将找出如何以最少的浪费来切割条形。

这是来自课程作业的规范。

引用： 现在，想象一下这样的场景：一家工厂生产长度为 150 毫米的钢筋。其切割车间收到棒材切割长度的订单，必须通过切割制造的棒材来满足该订单。对于每个订单，工厂都希望以产生最少浪费的方式切割棒材。

开发一种 java 方法，给定长度为 150mm 的已制造棒材、订单列表中所有订单的集合和一个空集，生成可以通过以最小浪费切割棒材来满足的订单集。 目前我已经让它以非递归方式工作，但不是 100%，当我尝试让它以递归方式工作时，我认为它只是崩溃了，哈哈，无限循环/堆栈溢出。

有人介意查看我的代码并帮助我吗？这是大学课程，也是我第一次真正尝试递归回溯，所以任何帮助都会很棒。

非递归代码可以工作。

代码：

private SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthLeft)
    {
        //SetInt possibleOrders = solution.clone();


        while(!possibleOrders.isEmpty())
        {

            if(possibleOrders.min()<= lengthLeft)
            {
                if(possibleOrders.min() > solution.min())
                {
                System.out.println(possibleOrders.min() + "added to solution \n");
                solution.add(possibleOrders.min());
                lengthLeft -= possibleOrders.min();
                possibleOrders.remove(possibleOrders.min());
                }
                else
                {
                    possibleOrders.remove(possibleOrders.min());
                }
                try{
                        Thread.sleep(10); //sleep 1000 milliseconds
                        }catch(Exception e){}
            }


            else if(possibleOrders.min() > lengthLeft)
            {
                System.out.println("poss order min" + possibleOrders.min()+"\n");
                System.out.println("solution min" + solution.min()+"\n");
                if(possibleOrders.min() > solution.min())
                {
                    int value = possibleOrders.min();
                    while(value > lengthLeft)
                    {
                        lengthLeft += solution.min();
                        System.out.println(solution.min() + "added to possible orders \n");
                        possibleOrders.add(solution.min());
                        solution.remove(solution.min());
                    }
                    solution.add(value);
                    possibleOrders.remove(value);
                    lengthLeft -= value;
                }
                else
                {
                    possibleOrders.remove(possibleOrders.min());
                }
            }

        }
        System.out.print("Solution :");
        solution.printNumbers();
        System.out.println("Wastage :" + lengthLeft);
        return solution;
    }

我对递归代码的尝试

private SetInt tryCutting(SetInt possibleOrders, SetInt solution, int lengthLeft)
    {
        while(!possibleOrders.isEmpty())
        {
            System.out.println("not empty");
            int value = possibleOrders.min();
            if(value < lengthLeft && value>solution.min())
            {
                solution.add(value);
                possibleOrders.remove(value);
                lengthLeft-=value;

                if(!possibleOrders.isEmpty())
                {
                    possibleOrders.tryCutting(possibleOrders,solution,lengthLeft);
                }
                else
                    break;
            }
        }
        return solution;
    }

Answer 1

这是我的解决方案。我没有使用集合，因为这会禁止订单多次出现相同的柱长度。不过，很容易将此示例改编为带有集合的版本。

import java.util.ArrayList;
import java.util.Arrays;

public class SteelMill {

    private int maximumLength;
    private Order best;

    public SteelMill() {
        Order ordered = new Order(3, 4, 1, 6, 2, 5);
        Order filled = new Order();
        maximumLength = 7;
        fillOrder(ordered, filled, 0);
        System.out.println("best solution found: " + best + " waste = "
                + (maximumLength - best.total()));
    }

    private void fillOrder(Order ordered, Order filled, int depth) {
        print(depth, "ordered = " + ordered + " filled = " + filled);
        depth++;
        if (filled.total() > maximumLength) {
            return;
        }
        if (filled.total() == maximumLength || best == null
                || filled.total() > best.total()) {
            best = filled;
            if (filled.total() == maximumLength) {
                System.out.println("perfect solution found: " + filled);
            }
        }
        for (Integer bar : ordered) {
            Order childOrdered = new Order(ordered);
            childOrdered.remove(bar);
            Order childFilled = new Order(filled);
            childFilled.add(bar);
            fillOrder(childOrdered, childFilled, depth);
        }
    }

    public class Order extends ArrayList<Integer> {
        private static final long serialVersionUID = 1L;

        public Order(Order toCopy) {
            super(toCopy);
        }

        public Order(Integer... values) {
            for (Integer value : values) {
                add(value);
            }
        }

        public int total() {
            int total = 0;
            for (Integer value : this) {
                if (value != null) {
                    total += value;
                }
            }
            return total;
        }

        public String toString() {
            return Arrays.toString(toArray());
        }
    }

    private static void print(int depth, String msg) {
        StringBuilder tabs = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            tabs.append("  ");
        }
        System.out.println(tabs + msg);
    }

    public static void main(String[] args) {
        new SteelMill();
    }
}