Recursion/Backtracking

[petreej]

I am making a program that determines an optimal layout for a given set of boards in constructing a table top. Variables include width and length that the table top must be. Boards are also given. For example, if I pass in a file that declares the table to be 2 width and 7 length and boards that consist of:
5 5 3 3 1. Then the optimal build is:

5 3
5 3

The waste is 2, which is the best. I am using an array to store the boards and using an array of linked lists to represent the table. Here is what I have so far. The recursion is far from working. I would appreciate some help or any idea's thanks.


public class LinkedList{
private Node head;
private Node tail;
private int size;

public LinkedList(){
head = tail = null;
size = 0;
}

/** Returns true if the list is empty, otherwise false */
public boolean isEmpty(){
// FIX:
return true;
}

/**
* Returns the word that is the first node in the list.
* If the list is empty, it throws a NullPointerException.
*/
public int peek(){
if (head == null)
throw new NullPointerException();
return head.info;
}

/**
* Add a new node to the end of the list whose
* word is str.
*/
public boolean add(int num){

Node n=new Node(num);
if(head==null)
head=n;
else
tail.next=n;

tail=n;
size++;
return true;
}




public void print(){
for (Node node = head; node!= null; node = node.next){
System.out.println(node.info);
}
}

public int sumList()
{
int sum=0;
for (Node node=head; node!=null; node = node.next)
sum=sum+node.info;
return sum;

}

public int getSize()
{
return size;
}

public int getNode(int j)
{
Node node=head;
for (int i=0; i<j; i++)
node = node.next;
return node.getInfo();
}



// : ~ : ~ : : ~ : ~ : ~ : ~ : ~ : ~ : ~ : ~
// inner class
class Node{
int info;
Node next;

public Node(int num){
info = num;
}

public int getInfo(){
return info;
}
}
}

import java.io.*;
import java.util.*;

public class TableProblem {

public LinkedList table[];
public int width, length, numBoards;
public int boards[];
public int board;


public TableProblem(int w, int l, int numB) {
width=w;
length=l;
numBoards=numB;
table=new LinkedList[width];
for (int i=0; i<width; i++)
table[i]=new LinkedList();
boards=new int[numBoards];
boards[0]=5;
boards[1]=2;
boards[2]=6;
boards[3]=4;

board=0;
}

public TableProblem(TableProblem tp) {
width=tp.width;
length=tp.length;
numBoards=tp.numBoards;
table=new LinkedList[width];
for (int i=0; i<width; i++) {
table[i]=new LinkedList();
for(int j=0; j<tp.table[i].getSize(); j++)
table[i].add(tp.table[i].getNode(j));
}
boards=new int[numBoards];
boards[0]=5;
boards[1]=2;
boards[2]=6;
boards[3]=4;

board=0;
}


public int waste() {

int area=width*length;
int allBoards=0;
for(int i=0; i<width; i++)
allBoards=allBoards+table[i].sumList();

return allBoards-area;
}


public boolean isBuilt() {
boolean isBuilt = true;
for(int i=0; i<width; i++)
if (table[0].sumList()<length)
isBuilt=false;

return isBuilt;
}
}

import java.io.*;
import java.util.*;

public class test{


private static TableProblem tp;
private static int bestWaste=100;
private static TableProblem curr;
private static TableProblem best;

public static void main(String[] args) throws Exception
{

tp=new TableProblem(1,10,4);

//tp.table[0].add(tp.boards[0]);
//tp.table[0].add(tp.boards[2]);
//tp.table[1].add(tp.boards[1]);
//tp.table[1].add(tp.boards[3]);

//TableProblem foo=new TableProblem(tp);

//foo.table[0].add(tp.boards[0]);
//foo.table[0].print();
//tp.table[0].print();
/*
System.out.println("TP Row 1: ");
tp.table[0].print();

System.out.println("Row 2: ");
tp.table[1].print();
System.out.println("Waste: " + tp.waste());
System.out.println("Row 1 Sum: " + tp.table[0].sumList());
System.out.println("Row 2 Sum: " + tp.table[1].sumList());

if (tp.isBuilt())
System.out.println("Built");
else
System.out.println("Not Built");

*/





System.out.println(findBestSolution(tp)
.waste());


}

public static TableProblem findBestSolution(TableProblem tp){

if (tp.waste() > bestWaste)
return null;
if (tp.isBuilt())
{
if (tp.waste()<bestWaste)
bestWaste=tp.waste();
best = null;

}
else
{

for(int i=0; i<tp.numBoards; i++) {
TableProblem foo=new TableProblem(tp);
foo.table[0].add(foo.boards[i]);
curr=findBestSolution(foo);
if(curr==null)
continue;
if(best==null)
best=curr;
else if (best.waste()>curr.waste())
best=curr;
}
}
return best;
}



}


Thanks