-1

尝试为 subsetSum 编写算法...它应该找到给定向量的所有可能子集，然后找到哪些子集加起来达到目标​​值。但是，我不断收到 nullpointerexceptions 和其他一些错误。有人可以帮我吗？我处于一个紧张的位置，大脑几乎无法运作。非常感激。谢谢。

java.lang.NullPointerException
at Sumation.subsetSum(Sumation.java:78)
at Sumation.main(Sumation.java:110)

第 78 行是 subsetSum 方法中第一个 for 循环的行。

/* Ruben Martinez
 * CS 210 Data Structures
 * Program requires no paramters at main method call;
 * instead, a JOptionPane asks for the ints the user
 * wishes to search. These must be seperated by commas,
 * e.g. 50,40,30 or 35,45,55. Program then asks for a 
 * target int to find. Program searches for target
 * and returns combinations that add up to the target.
 */

import java.util.Vector; 
import javax.swing.*;

public class Sumation
{
    static int[] array;
    static int target;
    static Vector<Integer> subsets;
    static Vector<Integer> set;
    static Vector<Vector<Integer>> outer;

    public Sumation() {
        //insert integers into array
        String defineArray = (String)JOptionPane.showInputDialog(null,
                "Enter integers to search. Seperate by commas.", null);
        //splits string into array delimeted by commas
        String[] arrayString = defineArray.split(",");
        //creates int array of size of string array
        array = new int[arrayString.length];
        //adds ints from args[] to int array
        for (int i = 0; i < arrayString.length; i++) {
            array[i] = Integer.parseInt(arrayString[i]);
        }
        //enter integer to search for
        String targetString = (String)JOptionPane.showInputDialog(null,
                "What is your target integer?", null);
        //turns string to int
        target = Integer.parseInt(targetString);


        set = new Vector<Integer>();
        for (int n = 0; n < array.length; n++) {
            set.add(array[n]);
        }
    }

    private static Vector<Vector<Integer>> getSubsets(Vector<Integer> set) {
        Vector<Vector<Integer>> subsetCollection = new Vector<Vector<Integer>>();

        if (set.size() == 0) {
            subsetCollection.add(new Vector<Integer>());
        } else {
            Vector<Integer> reducedSet = new Vector<Integer>();
            reducedSet.addAll(set);

            int first = reducedSet.remove(0);
            Vector<Vector<Integer>> subsets = getSubsets(reducedSet);
            subsetCollection.addAll(subsets);

            subsets = getSubsets(reducedSet);

            for (Vector<Integer> subset : subsets) {
                subset.add(0, first);
            }

            subsetCollection.addAll(subsets);
        }

        return subsetCollection;
    }

    public static Vector<Vector<Integer>> subsetSum(Vector<Integer> subsets, int target) {
        //creates outer vector
        outer = new Vector<Vector<Integer>>();

        for (int k = 0; k < subsets.size(); k++) {
            //if k is the target, display
            if (array[k] == target) {
                //creates new inner vector for values that equal target
                Vector<Integer> inner = new Vector<Integer>();
                outer.add(inner);
                //add k to vector
                inner.add(array[k]);
            }
            for (int l =0; l < subsets.size(); l++) {
                int sum = subsets.elementAt(k);
                if (sum == target) {
                    //creates new inner vector for values that sum up to target
                    Vector<Integer> inner = new Vector<Integer>();
                    outer.add(inner);
                    //add l,k to vector
                    inner.add(array[l]);
                    inner.add(array[k]);
                }
                else {
                    System.out.print("");
                }
            }
        }
        //return combinations that add up to target in vector form
        return outer;
    }

    public static void main(String[] args) {
        //calls sumation constructor
        Sumation s = new Sumation();
        s.getSubsets(set);
        s.subsetSum(subsets, target);
        JOptionPane.showMessageDialog(null, "The combinations that equal to "+target+" are \n"+outer, "Vector", JOptionPane.INFORMATION_MESSAGE);
    }
}
4

1 回答 1

0

您是如何尝试分析的？

如果您手头有调试器（即 IDE），那么分析此类问题非常容易。根据您的喜好，您可以

  • 从头到尾逐步执行程序
  • 在抛出异常的行设置断点
  • 设置断点为NullPointerExceptions

并且在所有情况下，您都可以轻松查看变量/字段的状态都是什么。如果您进入意外状态，您可以轻松地倒带或重新运行程序以查看先前计算的结果并注意它偏离您预期的地方。

即使您手头没有调试器，您也可以println每隔一段时间（并且绝对是在异常行之前）放入语句，以便查看值是什么 - 一个穷人的调试器。

但说真的，如果您要进行任何重要的 Java 开发，请设置一个真正的调试器。如果需要 5-20 分钟，并且在您第一次必须调查此类问题时会为您节省更多。

无论如何，问题是由于您从未向该字段分配任何内容这一事实引起的subsets，所以null当您将它传递给subsetSumin 时main。

这可能是因为方法中的subset局部变量会getSubsets影响它 - 如果您希望该方法修改该字段，那么您就错了。但是，无论如何，这将是不好的做法（恕我直言），因为在递归方法中像这样改变状态很容易出错，即使正确也会让人很难在任何时候推理类（因为你' d 需要知道它处于什么状态）。将结果分配给字段是初学者的常见错误（可能是因为它感觉更面向对象？），当更好的选择是让方法返回其结果时，通常将其存储在局部变量中。

所以main方法应该将getSubsets调用的结果分配给一个局部变量，然后将它传递给方法subsetSum。

（我注意到这些类型并不完全兼容——你确定参数不subsetSum应该是 a Vector<Vector<Integer>>too？目前看起来你只能传入一个子集。但那是另一回事。）

于 2011-10-20T10:33:06.820 回答