递归回溯帮助！ [英] Recursive backtracking help!
问题描述
我有点酸菜.我必须实现一个递归回溯算法，该算法将计算出如何以最少的浪费量切割条形.
I'm in abit of a pickle. I've got to implement a recursive backtracking algorithm that will work out how to cut a bar with the least ammount of wasteage.
这是来自课程作业的规范.
this is from the specification for the coursework.
引用:现在，想象一下工厂生产长度为 150mm 的钢筋的场景.其切割车间收到切割棒材长度的订单，必须通过切割制造的棒材来满足这一要求.对于每个订单，工厂都希望以这样一种方式切割棒材，以最大限度地减少浪费.
Quote: Now, imagine the scenario in which a factory manufactures steel bars of length 150mm. Its cutting shop receives orders for cut lengths of bars, which must be met by cutting up the manufactured bars. With each order the factory wants to cut the bar is such a way that it produces the least amount of wastage.
开发一个 java 方法，给定长度为 150mm 的制造棒材，订单列表中的所有订单的集合和一个空集，生成可以通过切割棒材以最小浪费来满足的订单集.目前我已经让它以非递归方式工作，但不是 100%，当我尝试让它以递归方式工作时，它只是崩溃了哈哈无限循环/堆栈溢出，我认为.
Develop a java method which given manufactured bar of length 150mm, a set of all orders in the order list and an empty set produces the set of orders which can be met by cutting up the bar with minimum wastage. currently I've sort of got it working non recursively but not 100% and when I try and get it working recurisvely it just crashed lol infinite loop / stack overflow I think.
有人介意看看我的代码并帮我一把吗?它用于 uni 课程，也是我第一次真正尝试递归回溯，因此任何帮助都会很棒.
Would anyone mind looking at my code and giving me a hand? its for uni coursework and its the first time i've really tryed recursive backtracking so any help would be brilliant.
那种有效的非递归代码.
Non recursive code that sort of works.
代码:
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;
}
推荐答案
这是我的解决方案.我没有使用集合，因为这会禁止多次出现相同长度的订单.不过，很容易将此示例应用于带有集合的版本.
Here's my solution. I didn't use sets because that would prohibit orders with multiple occurrences of the same bar length. It's easy to adapt this example to a version with sets though.
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();
}
}
这篇关于递归回溯帮助！的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
