如果不存在子集和等于一给定值，则返回最接近子集和将值 [英] If there is no subset sum equal to a given value, return subset sum closest to the value
问题描述
我工作的一个子集和问题，需要打印的子集和这是最接近的值，如果相等，则只打印值。只有正整数
如果存在多个子集总和是同样接近的值，
值= 10，subsetSum1 = 9，subsetSum2 = 11
打印总和那小于值
所以控制台应用程序认定的平等子集和完美，但我将如何去打印出的子集和那最接近值。
类节目
{
静态INT []元素;
静态int值;
静态布尔液= FALSE;
静态无效的主要（）
{
值= 10000;
Console.WriteLine（多少号？）;
INT elementsQty = int.Parse（到Console.ReadLine（））;
元素=新的INT [elementsQty]
的for（int i = 0; I< elementsQty;我++）
{
元素[I] = int.Parse（到Console.ReadLine（））;
}
Console.WriteLine（\\\
Output：）;
名单，LT; INT>集=新的List< INT>（）;
GetSubset（0，子集）;
如果
Console.WriteLine（不匹配）（解决方案！）;
到Console.ReadLine（）;
}
静态无效GetSubset（INT指数，列表与LT; INT> myElements）
{
如果（myElements.Sum（）==值和放大器;&安培; myElements .Count之间大于0）
{
Console.WriteLine（{0} = {1}，的string.join（+，myElements），值）;
液= TRUE;
}
的for（int i =指数; I< elements.Length;我++）
{
myElements.Add（元素[I]）;
GetSubset第（i + 1，myElements）;
myElements.RemoveAt（myElements.Count - 1）;
}
}
}
您当前的解决方案使用的回溯。这种方法的问题是，时间复杂性尺度的指数。这是不好的。从您进入元素的合理数量（如100+），你的程序是注定
鉴于你的整数列表都是（严格）阳性，更好的方法来做到这一点是使用动态的节目的
我们的想法是，如果你搜索一个总和的 K 的，你定义的内存的最多的 2 K + 1 的数组中的元素。最初，所有的存储元件都无效空，除非你存储一个空的集合元素索引 0 ，
所以最初的记忆是这样的：
7 - > _
6 - > _
5 - > _
4 - > _
3 - > _
2 - > _
1 - > _
0 - > []
如果 B = 8 （我们将使用 b = 8 通过这个答案的其余部分，但它当然只是一个例子）。
与 _ 什么（一空指针）和 [] 空集（不管是什么类型的集合）。
现在在你给出一组数字中的每个元素，请执行下列任务。您的迭代的结束内存中的所有有效的（不是空）的集合。对于每一个集合，你升级的集合：你制作一个副本，元素添加到集合，并将其存储到与新和的索引。如果已经有一个与该款项的集合，你没有做任何事情。这种迭代可以实现如下：
为（INT S = B-XI-1; S> = 0; S ！ - ）{
如果（COLS [S +玺] == NULL和放大器;&安培; COLS [S] = NULL）{
名单，LT; INT> CLN =新的List< INT>（COLS [S]）;
cln.Add（十一）。
COLS [S +玺] = CLN;
}
}
与喜我们希望添加的元素。因此，如果语句检查，如果有一笔集合取值是有效的（不是空），我们是否有创建一个新的集合：是否用得到的总和集合还不存在。在为回路设置界限：它是没有用的，升级的集合出界：这样既 S +喜和取值必须是有效的界限。这意味着取值已经从 0 到 B-XI-1 <范围（包括） / code>（含税）。我们不得不向后迭代，因为我们本来添加我们的元素喜第二次。
事实上，采取为例第一元素是 2 ，现在我们开始从 0 迭代（错误地）为 8 -2-1 = 5 。现在，这意味着，如果 S = 0 ，我们升级空集，所以现在的记忆是这样的：
7 - > _
6 - > _
5 - > _
4 - > _
3 - > _
2 - > [2]
1 - > _
0 - > []
（ [2] 是一个收集与 2 ）的为循环的下一个迭代， S = 1 ，我们看到有一笔存在一个没有收藏，所以我们继续下去，但现在 S = 2 和我们刚刚构建了这样的集合。关键在于，我们的算法没有做任何书签，从而将增加2秒时间导致：
7 - > _
6 - > _
5 - > _
4 - > [2,2]
3 - > _
2 - > [2]
1 - > _
0 - > []
现在人们可以做两件事：做书签哪些集合构建迭代，但需要额外的工作，或者一个可以遍历从高分到低分。由于所有的整数喜保证是积极的，我们知道我们不能升级，在收集向下的集合。如果我们按照正确的方式整个迭代中，事后的记忆是这样的：
7 - > _
6 - > _
5 - > _
4 - > _
3 - > _
2 - > [2]
1 - > _
0 - > []
如果下一个元素是 1 ，内存是这样的：
7 - > _
6 - > _
5 - > _
4 - > _
3 - > [2,1]
2 - > [2]
1 - > [1]
0 - > []
现在给出的下一个元素是 3 ，我们终于看到了动态规划的功率：
7 - > _
6 - > [2,1,3]
5 - > [2,3]
4 - > [1,3]
3 - > [2,1]
2 - > [2]
1 - > [1]
0 - > []
您会注意到，我们还没有构建一个集合 3 与 [3] ，因为已经有这样的集合。这可能看起来没有那么多令人印象深刻。但是，从来源所有集合[2,1] 现在不会有重复[3] 这将有一直是这样，如果一个使用的回溯的算法。
做这行的每一个元素后，内存为每个索引或者一种方式来创建一个与对应于索引总和子集，或空如果没有这样的子集可以被构造。现在，你可以简单地看看构造的藏品，并挑选一个最接近的 K 的。我们知道，这样的集合不同，最多的 K 的，因为空的集合有总和为零，因而不同的 K 的
整个故事可以用这个算法被告知：
静态列表< INT> GetSubset（int值，IEnumerable的< INT> XS）{
INT B = 2 *值;
名单，LT; INT> [] = COLS新的List< INT> [B]。
COLS [0] =新的List< INT>（）;
的foreach（在XS INT十一）{
为（INT S = B-XI-1; S> = 0; S--）{
如果（COLS [S +喜] == NULL和放大器;&安培; COLS [S] = NULL）{
名单，LT;！INT> CLN =新的List< INT>（COLS [S]）;
cln.Add（十一）。
COLS [S +玺] = CLN;
}
}
}
为（INT D = 0; D<价值; d ++）{$ B $ B如果（！COLS [价值-D] = NULL） {
返回COLS [价值-D]。
}否则如果（COLS [值+ D]！= NULL）{
返回COLS [值+ D]。
}
}
返回COLS [0];
}
的
列表< T> 办法是不是最有效：你可以使用的头尾列表的方法（但不幸的是，在.NET库似乎缺乏这一点）
演示（使用 CSHARP 交互式shell）：
$ CSHARP
单C＃壳牌，键入help;为帮助
输入下面的语句。
&CSHARP GT;公共类Foo {
>
>公共静态列表< INT> GetSubset（int值，IEnumerable的< INT> XS）{
> INT B = 2 *值;
>清单< INT> [] = COLS新的List< INT> [B]。
> COLS [0] =新的List< INT>（）;
>的foreach（在XS INT十一）{
>对于（INT S = B-XI-1; S> = 0; S--）{
>如果（COLS [S +玺] == NULL和放大器;&安培;！COLS [S] = NULL）{
>清单< INT> CLN =新的List< INT>（COLS [S]）;
> cln.Add（十一）。
> COLS [S +玺] = CLN;
> }
> }
> }
>对于（INT D = 0; D<价值; d ++）{$ B $ B>如果（COLS [价值-D]！= NULL）{
>返回COLS [价值-D]。
> }否则如果（COLS [值+ D]！= NULL）{
>返回COLS [值+ D]。
> }
> }
>返回COLS [0];
> }
> }
&CSHARP GT;
&CSHARP GT; INT [] =项新INT [] {2,3,5,7};
&CSHARP GT; Foo.GetSubset（8项）;
{3,5}
&CSHARP GT; Foo.GetSubset（7项）;
{2，5}
&CSHARP GT; Foo.GetSubset（9项）;
{2,7}
&CSHARP GT; Foo.GetSubset（6项）;
{2，3}
&CSHARP GT; Foo.GetSubset（10项）;
{2，3，5}
csharp的> Foo.GetSubset（11项）;
{2，3，5}
正如你所看到的 6 不能与这些整数形成，但可以拿出一套凝聚了以 5 。
这种方法的好处是，你需要做的搜索只有一次：你可以明显地打电话给你的方法，多次首先搜索的值的 K 的，然后的 K +1 的，然后的 K-1 的等。但问题是，这将导致计算上昂贵的方法
I am working on a subset sum problem, that needs to print the subset sum that's closest to the value, if equal then just print the value. Only positive integers
If there are multiple subset sums that are equally close to the value,
value = 10, subsetSum1 = 9, subsetSum2 = 11
print the sum thats less than the value.
So console app finds the equal subset sum perfectly, but how would I go about printing out the subset sum thats closest to the value.
class Program
{
static int[] elements;
static int value;
static bool solution = false;
static void Main()
{
value = 10000;
Console.WriteLine("How many numbers ?");
int elementsQty = int.Parse(Console.ReadLine());
elements = new int[elementsQty];
for (int i = 0; i < elementsQty; i++)
{
elements[i] = int.Parse(Console.ReadLine());
}
Console.WriteLine("\nOutput:");
List<int> subset = new List<int>();
GetSubset(0, subset);
if (!solution)
Console.WriteLine("No match");
Console.ReadLine();
}
static void GetSubset(int index, List<int> myElements)
{
if (myElements.Sum() == value && myElements.Count > 0)
{
Console.WriteLine(" {0} = {1}", string.Join(" + ", myElements), value);
solution = true;
}
for (int i = index; i < elements.Length; i++)
{
myElements.Add(elements[i]);
GetSubset(i + 1, myElements);
myElements.RemoveAt(myElements.Count - 1);
}
}
}
Your current solution makes use of backtracking. The problem with this approach is that the time complexity scales exponential. Which is not good: from the moment you enter a reasonable number of elements (like 100+), your program is doomed.
Given your list of integers are all (strict) positive, a better way to do this is using dynamic programming.
The idea is that if you search for a sum K, you define a memory of at most 2 K + 1 elements of lists. Initially all memory elements are invalid null, except the element index 0, where you store an empty collection.
So initially the memory looks like:
7 -> _
6 -> _
5 -> _
4 -> _
3 -> _
2 -> _
1 -> _
0 -> []
if b=8 (we will use b=8 through the remainder of this answer, but it is of course only an example).
with _ nothing (a null pointer), and [] an empty collection (regardless of what kind of collection).
Now for each element in your given set of numbers, you perform the following tasks. you iterate over all effective (not null) collections in memory. For each of the collections, you "upgrade" that collection: you make a copy, add the element to the collection, and store it into the index with the new sum. In case there is already a collection with that sum, you don't do anything. Such iteration can be implemented as follows:
for(int s = b-xi-1; s >= 0; s--) {
if(cols[s+xi] == null && cols[s] != null) {
List<int> cln = new List<int>(cols[s]);
cln.Add(xi);
cols[s+xi] = cln;
}
}
with xi the element we wish to add. The if statement thus checks if the collection with sum s is effective (not null) and whether we have to create a new collection: whether a collection with the resulting sum does not yet exists. The for loop sets bounds: it is no use to upgrade a collection out of bounds: so both s+xi and s must be valid bounds. This means s has a range from 0 (included) to b-xi-1 (included). We have to iterate backwards because we could otherwise add our element xi a second time.
Indeed, take as example that the first element is 2, now we start iterating (wrongly) from 0 to 8-2-1=5. Now that means that if s=0, we "upgrade" the empty collection, so now the memory looks like:
7 -> _
6 -> _
5 -> _
4 -> _
3 -> _
2 -> [2]
1 -> _
0 -> []
([2] is a collection with 2), the next iteration of the for loop, s=1 and we see no collection with sum one exists, so we continue, but now s=2 and we have just constructed such collection. The point is that our algorithm does not do any bookmarking, and thus would add 2 a second time resulting in:
7 -> _
6 -> _
5 -> _
4 -> [2,2]
3 -> _
2 -> [2]
1 -> _
0 -> []
Now one could do two things: do bookmarking about which collections are constructed that iteration, but that requires additional work, or one can iterate from high to low. Since all integers xi are guaranteed to be positive, we know we cannot "upgrade" a collection in the downwards collection. If we perform an entire iteration in the correct way, afterwards the memory looks like:
7 -> _
6 -> _
5 -> _
4 -> _
3 -> _
2 -> [2]
1 -> _
0 -> []
If the next element is 1, the memory looks like:
7 -> _
6 -> _
5 -> _
4 -> _
3 -> [2,1]
2 -> [2]
1 -> [1]
0 -> []
Now given the next element is 3, we finally see the power of dynamic programming:
7 -> _
6 -> [2,1,3]
5 -> [2,3]
4 -> [1,3]
3 -> [2,1]
2 -> [2]
1 -> [1]
0 -> []
You notice that we haven't constructed a collection for 3 with [3], because there is already such collection. This might look not that much impressive. But all collections that originate from [2,1] will now not have a duplicate with [3] which would have been the case if one uses a backtracking algorithm.
After doing this for every element, the memory for each index either a way to create a subset with a sum that corresponds to the index, or null if no such subset could be constructed. Now you can simply take a look at the constructed collections, and pick the one closest to K. We know such collection differs at most K, because the empty collection has sum zero and thus differs K.
The entire story can be told with this algorithm:
static List<int> GetSubset(int value, IEnumerable<int> xs) {
int b = 2*value;
List<int>[] cols = new List<int>[b];
cols[0] = new List<int>();
foreach(int xi in xs) {
for(int s = b-xi-1; s >= 0; s--) {
if(cols[s+xi] == null && cols[s] != null) {
List<int> cln = new List<int>(cols[s]);
cln.Add(xi);
cols[s+xi] = cln;
}
}
}
for(int d = 0; d < value; d++) {
if(cols[value-d] != null) {
return cols[value-d];
} else if(cols[value+d] != null) {
return cols[value+d];
}
}
return cols[0];
}
The List<T> approach is not the most efficient: you can use a head-tail list approach (but unfortunately, the .NET library seems to lack this).
Demo (using csharp interactive shell):
$ csharp
Mono C# Shell, type "help;" for help
Enter statements below.
csharp> public class Foo {
>
> public static List<int> GetSubset(int value, IEnumerable<int> xs) {
> int b = 2*value;
> List<int>[] cols = new List<int>[b];
> cols[0] = new List<int>();
> foreach(int xi in xs) {
> for(int s = b-xi-1; s >= 0; s--) {
> if(cols[s+xi] == null && cols[s] != null) {
> List<int> cln = new List<int>(cols[s]);
> cln.Add(xi);
> cols[s+xi] = cln;
> }
> }
> }
> for(int d = 0; d < value; d++) {
> if(cols[value-d] != null) {
> return cols[value-d];
> } else if(cols[value+d] != null) {
> return cols[value+d];
> }
> }
> return cols[0];
> }
> }
csharp>
csharp> int[] items = new int[] {2,3,5,7};
csharp> Foo.GetSubset(8,items);
{ 3, 5 }
csharp> Foo.GetSubset(7,items);
{ 2, 5 }
csharp> Foo.GetSubset(9,items);
{ 2, 7 }
csharp> Foo.GetSubset(6,items);
{ 2, 3 }
csharp> Foo.GetSubset(10,items);
{ 2, 3, 5 }
csharp> Foo.GetSubset(11,items);
{ 2, 3, 5 }
As you can see 6 cannot be formed with these integers, but one can come up with a set that sums up to 5.
An advantage of this approach is that you need to do the search only once: you could evidently call your method multiple times first search for the value K, then K+1, then K-1,etc. but the problem is that this will result in a computationally expensive method.
这篇关于如果不存在子集和等于一给定值，则返回最接近子集和将值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
