-1

サブセット内のすべての整数を追加して、合計がゼロになるかどうかを確認するコードを作成しようとしています。ここに私がこれまでに持っているものがあります

  /**
   * Solve the subset sum problem for a set of integer values.
   * 
   * @param t
   *          a set of integer values
   * @return <code>true</code> if there exists a non-empty subset of
   *         <code>t</code> whose elements sum to zero.
   */
  public static boolean subsetSum(Set<Integer> t) {
    return subsetSum(new ArrayList<Integer>(t), null);
  }

  /**
   * Computes the sum of two Integers where one or both references are null. If
   * both references are null then the result is null; otherwise the result is
   * an integer equal to <code>a + b</code> where null references are treated as
   * being equal to zero.
   * 
   * @param a
   * @param b
   * @return the sum of <code>a</code> and <code>b</code>
   */
  private static Integer add(Integer a, Integer b) {
    if (a == null && b == null) {
      return null;
    } else if (a == null) {
      return b;
    } else if (b == null) {
      return a;
    }
    return a + b;
  }

  /**
   * Recursive solution for the subset sum problem.
   * 
   * <p>
   * <code>currentSum</code> holds the value of the subset under consideration;
   * it should be <code>null</code> if the current subset is empty.
   * 
   * @param t
   *          a list containing unique integer values (a set of integers)
   * @param currentSum
   *          the current subset sum so far
   * @return <code>true</code> if there exists a subset of <code>t</code> such
   *         that the sum of the elements in the subset and
   *         <code>currentSum</code> equals zero.
   */

******** THIS IS THE PART I HAD TO EDIT *************
  private static boolean subsetSum(List<Integer> t, Integer currentSum) {
      currentSum = 0;
      for (int i = 0; i < t.size(); i++) {
          currentSum = currentSum + (Integer)(t.get(i));
      }
      if (Lab9W.add(currentSum, t.get(0)) == 0) {
          return true;
      }
      else if (Lab9W.add(currentSum, t.get(1)) == 0) {
          return true;
      } else if (Lab9W.add(-t.get(0),t.get(0)) == 0) {
          return true;
      }
      else {
          return false;
      }

  }

}

このコードの作成について私が受け取ったヒントは次のとおりです。

セットの最初の要素を最初に考えます。セットの最初と残りの部分集合がゼロの合計はありますか? セットの最初と残りの部分がないゼロのサブセットの合計はありますか? 2 または 3 のいずれかが true の場合は true を返し、それ以外の場合は false を返します

何か助けてください私は一日中試してきましたが、私の人生でそれを機能させることはできません。再帰では、メソッド自体を呼び出す方法がわかりません。

だから私の質問は、このメソッドを再帰的にどのように書くのでしょうか? メソッド全体は、サブセットの合計を追加し、それらがゼロに等しいかどうかを確認することになっています。

4

3 に答える 3

0

わかりました、再帰のためにこのようなことをすることができます

 private static boolean subsetSum(List<Integer> t, Integer sizeOfArray,Integer currentSum){

      if(sizeOfArray == -1)
      {
        if (Lab9W.add(currentSum, t.get(0)) == 0)
        {
            return true;
        }
        else if (Lab9W.add(currentSum, t.get(1)) == 0)
        {
            return true;
        }
        else if (Lab9W.add(-t.get(0),t.get(0)) == 0) 
        {
            return true;
        }
        else
        {
            return false;
        }

       return subsetSum(t,sizeOfArray - 1,currentSum + t.get(sizeOfArray));
 }

チェックせずに入力しましたが、それは一種の概念です。このアイデアで遊ぶ

最初の呼び出しは次のようになります 

subsetSum(array,array.size()-1,0); // i dont know if its array.size()-1 // it is...

// これもできます...

    // return sum of array
    public Integer subsetSum(List<Integer> t, Integer sizeOfArray) 
    {
        if(sizeOfArray == 0)
            return t.get(0);
        return subsetSum(t, sizeOfArray - 1) + t.get(sizeOfArray);
    }

//これで何とかできるようになりました

     public boolean check(List<Integer> t)
{
        Integer currentSum = subsetSum(t,t.size()-1); 

        if (Lab9W.add(currentSum, t.get(0)) == 0)
            {
                return true;
            }
            else if (Lab9W.add(currentSum, t.get(1)) == 0)
            {
                return true;
            }
            else if (Lab9W.add(-t.get(0),t.get(0)) == 0) 
            {
                return true;
            }
            else
            {
                return false;
            }
}
于 2013-03-26T01:35:29.200 に答える
0 
// return sum of array
    public Integer subsetSum(List<Integer> t, Integer sizeOfArray) 
    {
        if(sizeOfArray == 0)
            return t.get(0);
        return subsetSum(t, sizeOfArray - 1) + t.get(sizeOfArray);
    }
//now you can do this somewere

     public boolean check(List<Integer> t)
{
        Integer currentSum = subsetSum(t,t.size()-1); 

        if (Lab9W.add(currentSum, t.get(0)) == 0) // do something with these if statements
            {
                return true;
            }
            else if (Lab9W.add(currentSum, t.get(1)) == 0)
            {
                return true;
            }
            else if (Lab9W.add(-t.get(0),t.get(0)) == 0) 
            {
                return true;
            }
            else
            {
                return false;
            }
}
于 2013-03-26T02:24:27.800 に答える