サブセットの合計の負の値

Question

負の値と負のターゲットを扱う方法が不思議でしたが、私のプログラムはこれらの変数に負の値が指定されたときはいつでもインデックスの範囲外のインデックスを返します。私はhasSum関数がこのプロジェクトの負の値で動作する必要があります、私は正に仮定することはできません。

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

あなたはサブセットまたはサブアレーの合計を検索しようとしていますか？
例えば、サブセット、単純な再帰は、トリックを行うことができれば：

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 
} 

あなたはサブアレーを見つけようとしている場合、私はprefix sums、例えばを使用したい：

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; 
} 

私はScanner静的なイニシャライザ内の入力値を読み取ることは悪い考えです、なぜそれらをmain()に移動しないのですか？