Subsetsumme negative Werte

Question

Ich habe mich gefragt, wie man mit negativen Werten und einem negativen Ziel arbeiten soll. Im Moment gibt mein Programm Index außerhalb der Grenzen, wenn diesen Variablen negative Werte zugewiesen werden. Ich brauche meine hasSum-Funktion mit negativen Werten für dieses Projekt arbeiten, ich kann nicht einfach positiv annehmen.

import java.util.Stack; 
import java.util.Scanner; 

public class subsetSum { 
    static Scanner input = new Scanner(System.in); 
    static { 
     System.out.print("Enter the target (T)" + "\n"); 
    } 

    /** Set a value for target sum */ 
    static int TARGET_SUM = input.nextInt(); //this is the target 

    /** Store the sum of current elements stored in stack */ 
    static int sumInStack = 0; 

    Stack<Integer> stack = new Stack<Integer>(); 

    public static void main(String[] args) { 

     //the size is S 
     System.out.println("\n" + "Enter the size of the set (S)"); 
     int values = input.nextInt(); //size = "values" 

     //value of each size entry 
     System.out.println("\n" + "Enter the value of each entry for S"); 

     int [] numbers = new int[values]; 

     for(int i = 0; i < values; i++) //for reading array 
     { 
      numbers[i] = input.nextInt();     
     } 

     if(hasSum(numbers, TARGET_SUM)){ 
      System.out.println("\n" + "Can: "); 
      subsetSum get = new subsetSum(); // encapsulation 
      get.populateSubset(numbers, 0, numbers.length); 
     }else{ 
      System.out.println("\n" + "Cannot"); 
     } 
    } 

    //method based on dynamic programming O(sum*length) 
    public static boolean hasSum(int [] array, int sum) 
    { 
     int i; 
     int len = array.length; 
     boolean[][] table = new boolean[sum + 1][len + 1]; //this has to be changed for negative 

     //If sum is zero; empty subset always has a sum 0; hence true 
     for(i = 0; i <= len; i++){ 
      table[0][i] = true; 
     } 

     //If set is empty; no way to find the subset with non zero sum; hence false 
     for(i = 1; i <= sum; i++){ 
      table[i][0] = false; 
     } 

     //calculate the table entries in terms of previous values 
     for(i = 1; i <= sum; i++) 
     { 
      for(int j = 1; j <= len; j++) 
      { 
       table[i][j] = table[i][j - 1]; 
       if(!table[i][j] && i >= array[j - 1]){ 
        table[i][j] = table[i - array[j - 1]][j - 1]; 
       } 
      } 
     }  
     return table[sum][len]; //this has to be changed for negative 
    } 

    public void populateSubset(int[] data, int fromIndex, int endIndex) { 
     /* 
     * Check if sum of elements stored in Stack is equal to the expected 
     * target sum. 
     * 
     * If so, call print method to print the candidate satisfied result. 
     */ 
     if (sumInStack >= TARGET_SUM) { 
      if (sumInStack == TARGET_SUM) { 
       print(stack); 
      } 
      // there is no need to continue when we have an answer 
      // because nothing we add from here on in will make it 
      // add to anything less than what we have... 
      return; 
     } 

     for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) { 
      if (sumInStack + data[currentIndex] <= TARGET_SUM) { 
       stack.push(data[currentIndex]); 
       sumInStack += data[currentIndex]; 
       /* 
       * Make the currentIndex +1, and then use recursion to proceed 
       * further. 
       */ 
       populateSubset(data, currentIndex + 1, endIndex); 
       sumInStack -= (Integer) stack.pop(); 
      } 
     } 
    } 

    /** 
    * Print satisfied result. i.e. 5 = 1, 4 
    */ 
    private void print(Stack<Integer> stack) { 
     StringBuilder sb = new StringBuilder(); 
     for (Integer i : stack) { 
      sb.append(i).append(","); 
     } 
     // .deleteCharAt(sb.length() - 1) 
     System.out.println(sb.deleteCharAt(sb.length() - 1).toString()); 
    } 
} 

Answer 1

Versuchen Sie, eine Summe von Teilmenge oder Subarray zu finden?
Wenn eine Teilmenge, dann eine einfache Rekursion den Trick tun könnte, zum Beispiel:

public static boolean hasSum(int [] array, int sum) 
{ 
    return hasSum(array, 0, 0, sum); 
} 

private static boolean hasSum(int[] array, int index, int currentSum, int targetSum) { 
    if (currentSum == targetSum) 
     return true; 
    if (index == array.length) 
     return false; 
    return hasSum(array, index + 1, currentSum + array[index], targetSum) || // this recursion branch includes current element 
      hasSum(array, index + 1, currentSum, targetSum); // this doesn't 
} 

Wenn Sie eine Subarray zu finden sind versucht, ich prefix sums verwenden würde, zum Beispiel:

public static boolean hasSum(int [] array, int sum) 
{ 
    int[] prefixSums = new int[array.length]; 
    for (int i = 0; i < prefixSums.length; i++) { 
     prefixSums[i] = (i == 0) ? array[i] : array[i] + prefixSums[i - 1]; 
    } 

    for (int to = 0; to < prefixSums.length; to++) { 
     if (prefixSums[to] == sum) 
      return true; // interval [0 .. to] 
     for (int from = 0; from < to; from++) { 
      if (prefixSums[to] - prefixSums[from] == sum) 
       return true; // interval (from .. to] 
     } 
    } 
    return false; 
} 

BTW Ich denke, das Lesen der Eingabewerte von Scanner innerhalb der statischen Initialisierung ist eine schlechte Idee, warum verschieben Sie sie nicht auf main()?