J'essaie de créer une structure de données arborescente récursive pour le problème suivant: étant donné un ensemble d'entiers positifs (éléments avec des valeurs positives), je veux diviser les dans un nombre fixe de sous-ensembles (les mettre dans des conteneurs ou des bacs) de sorte que la somme des éléments dans tous les sous-ensembles est égale.Structure arborescente récursive - Méthode de redémarrage/récursion d'appel dans l'espace if (___)
Par souci de simplicité, j'ai renommé tous les attributs. J'ai une classe de noeud ici qui contient tous les nœuds enfants respectifs et appelle leur fonction insert(). Si mon cas de base de succès (Tous les articles ont été distribués) est satisfait, tout ce qui m'importe c'est d'imprimer l'état actuel et de terminer ma fonction récursive.
Fondamentalement, dans chaque nœud, j'essaie de placer un élément dans un conteneur. Si elle échoue (parce que l'élément (ou Integer) dépasse la valeur maximale autorisée), je veux que le nœud parent crée un nouveau nœud et réessaye l'opération. avec son prochain conteneur. Si tous les conteneurs ont été testés, renvoyez false.
Malheureusement, je me bats avec deux choses. Voici le 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;
}
}
}
Problème Un:
`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
fait référence à cette
//If Child Returns False, Try Next Child boolean test = children.get(containercount).insert(containerlist, items)
Et Problème 2:
insert();
Fondamentalement, ce que je tente est juste redémarrer la même méthode avec le paramètre containercount à +1. Cependant quand j'appelle insert(), je crée vraiment une nouvelle méthode, donc je sens que je ne fais pas quelque chose de bien.
Toute aide est grandement appréciée. Je vous remercie.
Modifier: Articles de classe
package DataStructure_Finding_Equal_Sharings_444_Prjct3;
import java.util.ArrayList;
import java.util.List;
public class Items {
private ArrayList<Item> items;
private int totalCount;
private int totalvalue;
public Items(){
this.items = new ArrayList<>();
this.totalCount = 0;
this.totalvalue = 0;
}
public void addItem(int value){
this.items.add(new Item(value));
}
public void returnitem(Item item){
items.add(item);
}
public Coin takeItem(){
Coin tempItem = items.get(0);
items.remove(0);
return tempItem;
}
public int getTotalCount(){
return this.totalCount;
}
public int getTotalvalue(){
return this.totalvalue;
}
public List getAllItems(){
return items;
}
}
classe Container:
package ultimatetalerproblem;
import java.util.ArrayList;
import static java.util.Collections.list;
import java.util.List;
/**
* An Container holding items.
* <br/>
* The number of items it can hold is not limited, but the added value of the
* items it holds may not be higher than the given maximal size.
*/
public class Container {
/**h
* maximal allowed added value of items.
*/
private int totalValue;
/**
* current added value of items.
*/
private int currentSize;
/**
* list of items in container.
*/
private List<Item> items;
/**
* construct new container with given maximal size.
*
* @param totalValue
* @param subListValue
*/
public Container(int subListValue) {
this.totalValue = subListValue;
this.currentSize = 0;
this.items = new ArrayList<>();
}
/**
* adds given item to this container, and increases the currentSize of the container by
* value of item. If item does not fit, it will not be put in the container and
* false will be returned.
*
* @param item item to put in container
* @return true if item fit in container, false otherwise
*/
public boolean giveItem(Item item) {
if (currentSize + item.getValue() <= totalValue) {
items.add(item);
currentSize += item.getValue();
return true;
} else {
return false; // item didn't fit
}
}
/**
* removes given item from container and reduces the currentSize of the container by
* value of item.
*
* @param item item to remove from container
* @return wheter item was succesfully removed.
*/
/**
* returns the number of items in this container (NOT the added value of the
* items).
*
* @return number of items in this container
*/
public int numberOfItems() {
return items.size();
}
public int getTotalValue(){
return totalValue;
}
public List<Item> getitems(){
return items;
}
@Override
public String toString() {
String res = "";
for (int i = 0; i < items.size(); i++) {
res += items.get(i) + " ";
}
res += " Size: " + currentSize + " (max: " + totalValue + ")";
return res;
}
}