印刷するすべてのサブセット

Question

：

using System; 

namespace ProgrammingBasics 
{ 
    class Exercise 
    { 
     static void Main() 
     { 
      PrintArray(arr); 
      SubarrayWithSum(); 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Data members. 

     */ 
     // targer array 
     static int[] arr = { 2, 1, 2, 4, 3, 5, 2, 6 }; 
     // target sum 
     static int sum = 14; 

     //-------------------------------------------------------------------- 

     /* 
      Method: IsSubarrayWithSum(arr, sum); 

      It returns a bool value that indicates 
      whether there is a subarray within arr 
      with elements that sum up to specific value. 
     */ 
     static void SubarrayWithSum() 
     { 
      int depth = 0; 
      int startIndex = 0; 
      int endIndex = 1; 

      CheckAllCombinations(new int[arr.Length], startIndex, endIndex, depth); 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Method: CheckAllCombinations(subarray, sum); 

     */ 
     static void CheckAllCombinations(int[] subarray, int startIndex, int endIndex, int depth) 
     { 
      if (depth >= arr.Length) 
      { 
       return; 
      } 
      //Console.ReadKey(); 
      for (int i = startIndex; i < endIndex; i++) 
      { 
       subarray[i] = arr[i]; 
       //Console.WriteLine("startIndex = {0}, depth = {1}, i = {2}", startIndex, depth, i); 
       if (IsWantedSum(subarray)) 
       { 
        Console.Write("S = {0} -> yes", sum); 
        PrintSubArray(subarray); 
       } 
       //PrintArray(subarray); 
       //Console.ReadKey(); 
       CheckAllCombinations(new int [arr.Length], startIndex += 1, endIndex = (endIndex < arr.Length)? endIndex + 1 : endIndex, depth += 1); 
      } 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Method: IsWantedSum(int[] arr) 

     */ 
     static bool IsWantedSum(int[] arr) 
     { 
      int currentSum = 0; 

      for (int i = 0; i < arr.Length; i++) 
      { 
       currentSum += arr[i]; 
      } 

      if (currentSum == sum) 
      { 
       return true; 
      } 
      else 
      { 
       return false; 
      } 
     } 

     //-------------------------------------------------------------------- 
     /* 
      Method: PrintArray(); 

     */ 
     static void PrintArray(int[] subarray) 
     { 
      Console.Write("{"); 
      for (int i = 0; i < subarray.Length; i++) 
      { 
       Console.Write(subarray[i]); 
       if (i < subarray.Length -1) Console.Write(", "); 
      } 
      Console.WriteLine("}"); 
     } 

     //-------------------------------------------------------------------- 
     /* 
      Method: PrintSubArray(); 

     */ 
     static void PrintSubArray(int[] subarray) 
     { 
      Console.Write("("); 
      for (int i = 0; i < subarray.Length; i++) 
      { 
       if (subarray[i] != 0)Console.Write(subarray[i]); 
       if (subarray[i] != 0 && i < subarray.Length - 1) Console.Write(" + "); 
      } 
      Console.WriteLine(" = {0})", sum); 
     } 
    } 
} 

私は幾分一部正しい結果を得ている：

{2、1、2、4、3、5、2、6}
S = 14 - >はい（4 + 3 + 5 + 2 + = 14）
S = 14 - はい（2 + 4 + 3 + 5 + = 14）S = 14 - > yes（4 + 3 + 5 + 2 + = 14）
S = 14 - > yes（2 + 3 + 5 + 2 + 14） + 4 + 3 + 5 + = 14）
S = 14 - >はい（4 + 3 + 5 + 2 + = 14）

重複とそのように非連続的な要素のサブアレイを逃します：

はい（1 + 2 + 5 + 6 = 14）

誰かが私のアルゴリズムの問​​題のヒントを教えてくれますか？おそらく修正/新しい実装を提案することができますか？

Answer 1

OKは、ここで簡単に私は問題を理解し、基本的なソリューションを実装するために通過した情報を記述するための小さな試みです。

それはThe Subset Sum Problemが、我々は、特定の下容量を重量と呼ばれる値を保持したまま利益を最大化するために検索するが、私たちの場合、利益と軽量されているKnapsack Problemの特殊なケースと考えられていることが判明各値に関連付けられています。

は「ナップザック問題」で説明した偉大な様々なソリューションがあります - ケラー、Pferschy、Pisinger、しかし、私は実装と複雑持ち歩きません、理解できる最も簡単な解決策を当分の間、および/または有効性は、次のようになります。

PrintSubArray(subArray);は subArrayで trueが付い arrのすべての要素を出力します

//-------------------------------------------------------------------- 

    /* 
     Method: FindSubArray(); 

     Base case: - if current sum == targer sum: print current elements. 
        - if index == arr.Length: terminate search. 

     Recursive step: 
        - do not/select element with index and do not/update the current sum; recursive call with updated current sum and index. 
    */ 
    static void FindSubArray(int index, int currentSum, bool[] subArray) 
    { 
     // base case 
     if (currentSum == targetSum) 
     { 
      PrintSubArray(subArray); 
     } 
     else if (index == arr.Length) 
     { 
      return; 
     } 
     else 
     { 
      // recursive calls 
      subArray[index] = true; 
      currentSum += arr[index]; 
      FindSubArray(index + 1, currentSum, subArray); 

      currentSum -= arr[index]; // restore previous value of the sum signifying: element not selected 
      subArray[index] = false; 
      FindSubArray(index + 1, currentSum, subArray); 
     } 
    } 

。

出力：

{2、1、2、4、3、5、2、6}
S = 14 - >はい（2 + 1 + 2 + 4 + 3 + 2 + （2 + 1 + 2 + 3 + 6 = 14）
S = 14 - > yes 14 => yes（2 + 1 + 3 + 2 + 6 = 14）
S = 14 - > yes（2 + 1 + 4 + 5 + 2 + 1 + 5 + 6 = 14）
（2 + 2 + 3 + 5 + 2 + = 14）
S = 14 - >はい（2 + 2 + 4 + 6 = 14） （1 + 2 + 4 + 5 + 2 + = 14） S = 14 - > yes
S = 14 - >はい（1 + 2 + 3 + 2 + 6 = 14）
S = 14 - >はい（1 + 2 + 5 + 6 = 14）
S = 14 - >はい（2 + 4 + 3 + 5 + = 14）
S = 14 - > yes（2 + 4 + 3 + 5 + = 14）
S = 14 - >はい（2 + 4 + 2 + 6 = 14）
S = 14 - >はい（4 + 3 + 5 + 2 + = 14）
S = 14 - >はい（3 + 5 + 6 = 14）

---

1. 私は単に状態に問題を読んでいる本：特定の値」にまとめる要素を持つサブ配列がある場合は、「検索。

Answer 2

ここでは、組み合わせで簡単に行う方法を示します。おそらく、それらを保存するためのより良い方法があります（私はあなたが既に持っているすべてのサブ合計をエンコードする辞書を使用して考えています）。最後に、非連続要素を考慮する場合は、この場合は可能なサブ配列を取得する必要があります。連続した選択肢を見るだけではありません。組み合わせアルゴリズムのクレジットはojlovecd hereです。

class Exercise 
    { 
     static void Main() 
     { 
      PrintArray(arr); 
      // SubarrayWithSum(); 


      var result = GetCombination(arr); 

      foreach(var list in result) 
      { 
       var total = list.Sum(); 
       if (total == sum) 
        PrintArray(list); 
      } 
     } 
     static List<int> arr = new List<int> { 2, 1, 2, 4, 3, 5, 2, 6 }; 
     static int sum = 14; 

     static List<List<int>> GetCombination(List<int> list) 
     { 
      var result = new List<List<int>>(); 
      result.Add(new List<int>()); 
      double count = Math.Pow(2, list.Count); 
      for (int i = 1; i <= count - 1; i++) 
      { 
       string str = Convert.ToString(i, 2).PadLeft(list.Count, '0'); 
       for (int j = 0; j < str.Length; j++) 
       { 
        if (str[j] == '1') 
        { 
         result[i - 1].Add(list[j]); 
        } 
       } 
       result.Add(new List<int>()); 
      } 
      return result; 
     } 

     static void PrintArray(List<int> subarray) 
     { 
      Console.Write("{"); 
      for (int i = 0; i < subarray.Count; i++) 
      { 
       Console.Write(subarray[i]); 
       if (i < subarray.Count - 1) Console.Write(", "); 
      } 
      Console.WriteLine("}"); 
     } 
    } 

Answer 3

追加しているアレイにゼロがあるため、重複が発生していると思います。より速く実行される更新されたコードを参照してください。

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Text.RegularExpressions; 

namespace ProgrammingBasics 
{ 
    class Exercise 
    { 
     static void Main() 
     { 
      PrintArray(arr); 
      SubarrayWithSum(); 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Data members. 

     */ 
     // targer array 
     static int[] arr = { 2, 1, 2, 4, 3, 5, 2, 6 }; 
     // target sum 
     static int sum = 14; 

     //-------------------------------------------------------------------- 

     /* 
      Method: IsSubarrayWithSum(arr, sum); 

      It returns a bool value that indicates 
      whether there is a subarray within arr 
      with elements that sum up to specific value. 
     */ 
     static void SubarrayWithSum() 
     { 
      int depth = 0; 
      int endIndex = arr.Length - 1; 

      CheckAllCombinations(new int[arr.Length], depth); 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Method: CheckAllCombinations(subarray, sum); 

     */ 
     static void CheckAllCombinations(int[] subarray, int depth) 
     { 
      //Console.ReadKey(); 
      for (int i = depth; i < arr.Length; i++) 
      { 
       subarray[depth] = arr[i]; 
       Console.WriteLine("depth = {0}, i = {1}, array = '{2}' ", depth, i, string.Join(",", subarray.Select(x => x.ToString()).ToArray())); 
       int currentSum = subarray.Take(depth + 1).Sum(); 
       if (currentSum == sum) 
       { 
        Console.Write("S = {0} -> yes : ", sum); 
        Console.WriteLine(string.Join(",", subarray.Take(depth + 1))); 
       } 
       //PrintArray(subarray); 
       //Console.ReadKey(); 
       if (currentSum < sum) 
       { 
        CheckAllCombinations(subarray, depth + 1); 
       } 
      } 
     } 
     //-------------------------------------------------------------------- 

     /* 
      Method: IsWantedSum(int[] arr) 

     */ 

     //-------------------------------------------------------------------- 
     /* 
      Method: PrintArray(); 

     */ 
     static void PrintArray(int[] subarray) 
     { 
      Console.Write("{"); 
      for (int i = 0; i < subarray.Length; i++) 
      { 
       Console.Write(subarray[i]); 
       if (i < subarray.Length - 1) Console.Write(", "); 
      } 
      Console.WriteLine("}"); 
     } 

     //-------------------------------------------------------------------- 
     /* 
      Method: PrintSubArray(); 

     */ 
     static void PrintSubArray(int[] subarray) 
     { 
      Console.Write("("); 
      for (int i = 0; i < subarray.Length; i++) 
      { 
       if (subarray[i] != 0) Console.Write(subarray[i]); 
       if (subarray[i] != 0 && i < subarray.Length - 1) Console.Write(" + "); 
      } 
      Console.WriteLine(" = {0})", sum); 
     } 
    } 
}