mercredi 7 juin 2017

Recursive Tree Structure - Restarting method / calling recursion inside the if(___) space

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