I am trying to create a recursive tree data structure for following problem: given a set of positive integers (Items with positive values), I want to divide them into a fixed number of subsets (put them in Containers or bins) so that the sum of the elements in all subsets is equal.
For simplicity purpose I have renamed all attributes. I have a Node Class here that holds all the respective children nodes and calls their insert() function. If my success base case (All items have been distributed) is met, all I care about is printing the current state and ending my recursive function.
Basically in each node I try to place one item into a container. If it fails (because the item (or Integer) exceeds the maximum allowed value), I want the parent node to create a new node and reattempt the thing. with its next container. If all containers have been tested, return false.
Unfortunately, I am struggling with two things. Here's the Code.
package DataStructure_Finding_Equal_Sharings_444_Prjct3;
import java.util.ArrayList;
import java.util.List;
public class Node {
//List Holding Items still needed to be distributed
private Items items;
private List<Node> children;
private List<Container> containerlist;
private int containercount = 0;
private Item nodeItem;
public Node(List <Container> containerlist, Items item){
this.Items = item;
this.containerlist = containerlist;
this.children = new ArrayList<>();
}
public boolean insert(){
//BASECASE 1 : Combination Found
if(items.getAllItems().isEmpty()){
System.out.println("Combination Found:" + containerlist.toString());
return true;
}
//BASECASE 2 : All Children Created, All Container attempted to fill
else if (containercount +1 == containerlist.size()){
return false;
}
else{
//Check If This Node has been Initiated already. If Not, Initiate by Taking Item
if(nodeItem == null){
nodeItem = items.takeItem();
//If True (GiveItem was Succesful), Item is Stored in this Node. Afterwards New Node will be created.
if(containerlist.get(containercount).giveItem(nodeItem)){
Node childNode = new Node(containerlist, items);
children.add(childNode);
//If Child Returns False, Try Next Child
boolean test = children.get(containercount).insert(containerlist, items);
if( test == false){
containercount++;
insert();
return false;
}
//Child Returns True: Solution Found!
else{
return true;
}
}
//If False, Item did not fit in this Node, tell parent this child is dead. Put Item Item Back (This Never Happened)
else{
items.returnItem(nodeItem);
return false;
}
}
//Item was already assigned to Node, this is a revisited node
else {
//Create the next Node for another attempt
Node childNode = new Node(containerlist, items);
children.add(childNode);
//If Child Returns False, Try Next Child
if(childNode.insert() == false){
containercount++;
insert(); //Restart this node method with containercount increased, so that a new attempt can be made
return false; //end this attempt
}
else{
return true;
}
}
}
Problem One:
`Exception in thread "main" java.lang.RuntimeException: Uncompilable source code `
- Erroneous sym type:
ultimatetalerproblem.Node.insert at DataStructure_Finding_Equal_Sharings_444_Prjct3.Node.insert(Node.java:60[...]
Users/Library/Caches/NetBeans/8.1/executor-snippets/debug.xml:83: Java returned: 1
Is referring to this
//If Child Returns False, Try Next Child boolean test = children.get(containercount).insert(containerlist, items)
And Problem 2:
insert();
Basically what I am attempting is to just restart the same method with the parameter containercount set to +1. However when I call insert(), I am really creating a new method, so I feel like I am not doing something right.
Any help is greatly appreciated. Thank you.
Aucun commentaire:
Enregistrer un commentaire