Обновлено: subsetSum

Question

Попытка написать алгоритм для subsetSum ... Он должен найти все возможные подмножества данного вектора, а затем найти, какие из них складываются в целевое значение. Тем не менее, я продолжаю получать nullpointerexceptions и несколько других ошибок. Кто-нибудь может мне помочь? Я в затруднительном положении, мозг почти не функционирует. Очень признателен. Спасибо.

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

Строка 78 - это строка первого цикла for в методе subsetSum.

/* 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);
    }
}

Answer 1

Как вы пытались проанализировать это?

Если у вас есть отладчик (то есть IDE), анализировать подобные проблемы очень легко.В зависимости от ваших предпочтений, вы можете

• Пошагово выполнять программу от начала до конца
• Установить точку останова на строке, в которую выдается исключение
• Установить точку останова дляNullPointerExceptions

и во всех случаях вы легко увидите, в каком состоянии переменных / полей находятся все точки.Если вы попали в неожиданное состояние, программу можно легко перемотать или запустить заново, чтобы увидеть результаты предыдущих расчетов и посмотреть, где она отклоняется от ваших ожиданий.

Даже если у вас нет отладчика,Вы можете помещать println операторы в очень часто (и определенно непосредственно перед строкой исключения), чтобы увидеть, какие значения - отладчик бедняка.

А если серьезно, установите настоящий отладчик, есливы будете заниматься любой нетривиальной Java-разработкой.Если это займет 5-20 минут и сэкономит вам больше, чем в первый раз, когда вам придется исследовать проблему, подобную этой.

---

В любом случае, проблема вызвана тем, что вы никогда ничего не назначаетеполе subsets, поэтому null при передаче его в subsetSum в main.

Это может быть потому, что локальная переменная subset в методе getSubsets затеняет его - есливы ожидали, что этот метод изменит поле, тогда вы ошибетесь.Но тогда, в любом случае, это было бы плохой практикой (ИМХО), поскольку такое изменение состояния в рекурсивном методе было бы очень легко ошибиться, и даже если правильное значение, в любой момент будет трудно рассуждать о классе (как выМне нужно знать, в каком он был состоянии).Присвоение результатов полям - распространенная ошибка новичка (возможно, потому, что он чувствует себя более объектно-ориентированным?), Когда лучшим вариантом является метод , возвращающий его результат, который затем обычно сохраняется в локальной переменной.

Таким образом, метод main должен присвоить результат вызова getSubsets локальной переменной, а затем передать this в метод subsetSum.

(Я заметил, что типы не полностью совместимы - вы уверены, что аргумент subsetSum тоже не должен быть Vector<Vector<Integer>>? В настоящий момент похоже, что вы могли передать только одно подмножество. Но этодругое дело.)