打印总和为特定值的所有子集
本文关键字：子集 打印 | 更新日期: 2023-09-27 18:03:31
我已经尝试了一段时间了，现在找到所有元素(包括非连续的)的数组，求和为特定的值:
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)
(2 + 4 + 3 + 5 + = 14)
S = 14 ->是(4 + 3 + 5 + 2 + = 14)
S = 14 ->是(4 + 3 + 5 + 2 + = 14)
(2 + 4 + 3 + 5 + = 14)
S = 14 ->是(4 + 3 + 5 + 2 + = 14)
具有重复和缺失的非连续元素子数组，例如:
yes (1 + 2 + 5 + 6 = 14)
有没有人能给我一个关于我的算法问题的提示，并可能建议一个纠正/新的实现?
这里有一个简单的方法来处理组合。可能有一种更好的方法来存储它们(我在考虑使用字典来编码您已经拥有的所有子和)。在一天结束的时候，如果你想要考虑非连续的元素，你将不得不得到在这种情况下可能的子数组，而不仅仅是看连续的选择。组合算法的功劳在这里要归功于ojlovecd。
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("}");
}
}
我认为重复发生是因为你要添加的数组中有0。查看运行速度更快的更新代码。
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);
}
}
}
好的，这里是一个小小的尝试，简要描述我所经历的信息，以理解问题1和实现一个基本的解决方案。
结果表明子集和问题被认为是背包问题的一种特殊情况，其中我们在特定容量下寻找最大化利润同时保持权重的值，但在我们的情况下，与每个值相关的利润和权重是相同的。
在"背包问题"中描述了各种各样的伟大解决方案- Keller, Pferschy, Pisinger，然而，目前我能实现和理解的最简单的解决方案，不带复杂性和/或有效性，看起来像这样:
//--------------------------------------------------------------------
/*
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);
}
}
其中PrintSubArray(subArray);打印出subArray中所有标记为true的arr元素。
{2,1,2,4,3,5,2,6}
(2 + 1 + 2 + 4 + 3 + 2 + = 14)
(2 + 1 + 2 + 4 + 5 + 1)
(2 + 1 + 2 + 3 + 6 = 14)
(2 + 1 + 4 + 5 + 2 + = 14)
(2 + 1 + 3 + 2 + 6 = 14)
(2 + 1 + 5 + 6 = 14)
(2 + 2 + 4 + 6 = 14)
S = 14 ->是(2 + 2 + 3 + 5 + 2 + = 14)
(2 + 4 + 3 + 5 + = 14)
S = 14 -> yes (2 + 4 + 2 + 6 = 14)
(1 + 2 + 4 + 5 + 2 + = 14)
S = 14 -> yes (1 + 2 + 3 + 2 + 6 = 14)
S = 14 -> yes (1 + 2 + 5 + 6 = 14)
S = 14 -> yes (1 + 4 + 3 + 6 = 14)
S = 14 -> yes (1 + 5 + 2 + 6 = 14)
(2 + 4 + 3 + 5 + = 14)
S = 14 -> yes (2 + 4 + 2 + 6 = 14)
S = 14 ->是(4 + 3 + 5 + 2 + = 14)
S = 14 -> yes (3 + 5 + 6 = 14)
- 我正在阅读的书将问题简单地描述为:"查找是否有一个子数组，其元素之和为特定值'。