我正在尝试为以下问题创建一个递归树数据结构:给定一组正整数(具有正值的项目(,我想将它们分为固定数量的子集(将它们放入容器或垃圾箱中(,以使所有子集中的元素之和相等。
出于简单目的,我重命名了所有属性。我在这里有一个节点类,该课程包含所有各自的儿童节点,并称其插入((函数。如果我的成功基本案例(所有项目都已经分发(,我关心的只是打印当前状态并结束我的递归功能。
基本上,我尝试将一个项目放入容器中。如果失败(因为项目(或整数(超过最大值值(,我希望父节点创建一个新的节点并重新计算事物。带有下一个容器。如果所有容器都已测试,请返回false。
不幸的是,我正在为两件事而苦苦挣扎。这是代码。
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;
}
}
}
问题一:
`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
是指此
//If Child Returns False, Try Next Child
boolean test = children.get(containercount).insert(containerlist, items)
和问题2:
insert();
基本上,我正在尝试的是,将相同的方法重新启动使用参数containercount
设置为 1。但是,当我调用insert((时,我真的在创建一种新方法,所以我觉得自己做不到的事情。
任何帮助将不胜感激。谢谢。
编辑:项目类
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;
}
}
容器类:
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;
}
}
我到目前为止发现错误:
1(由于我没有项目类,所以我更改为整数。
2(在节点构造函数中,应该是这个。
您应该删除硬币并使用项目。