如果没有子集和等于给定值，返回最接近该值的子集和我在做研究子集求和问题，需要打印最接近该值的子集和，只有相等才打印该值。只有正整数如果有多个子集和等于这个值，value=10,subsetSum1=9,subsetSum2=11打印小于这个值的和。因此，控制台应用程序可以完美地找到相等的子集总和，但我如何打印出最接近该值的子集总和。类程序{静态int[]元素；静态整数值；静态布尔解决方案=假；静态无效主要（）{值=10000;Console.WriteLine("有多少个数字？");intelementsQty=int.Parse(Console.ReadLine());elements=newint[elementsQty];对于(inti=0;i0){Console.WriteLine("{0}={1}",string.Join("+",myElements),值);解决方案=真；}for(inti=index;i_6->_5->_4->_3->_2->_1->_0->[]如果b=8（我们将剩下的答案使用b=8，但这当然只是一个例子）。with_nothing(nullpointer)和[]空集合（不管是什么类型的集合）。现在，对于给定数字集中的每个元素，执行以下任务。遍历内存中的所有有效（非空）集合。对于每个集合，您“升级”集合：创建一个副本，将元素添加到集合中，然后将其与新的总和一起存储到索引中。如果具有该总和的集合已经存在，则不执行任何操作。该迭代可以按如下方式实现：for(ints=b-xi-1;s>=0;s--){if(cols[s+xi]==null&&cols[s]!=null){列表cln=newList(cols[s]);cln.Add(xi);cols[s+xi]=cln;}}我们想用xi添加元素。因此if语句检查具有sum的集合是否有效（非空）以及是否必须创建一个新集合：具有结果总和的集合尚不存在。for循环设置边界：将集合提升为边界是没有用的：因此s+xi和s必须是有效边界。这意味着s的范围从0（含）到b-xi-1（含）。我们必须向后迭代，否则我们可能会第二次添加元素xi。实际上，以第一个元素为2为例，现在我们开始从0开始迭代到8-2-1=5（错误）。现在这意味着如果s=0，我们“升级”空集合，所以现在内存看起来像：7->_6->_5->_4->_3->_2->[2]1->_0->[]（[2]是一个包含2的集合），for循环的下一次迭代，s=1，我们没有看到有一个包含sum的集合，所以我们继续，但是现在s=2，我们只是构建了这样一个集合。关键是我们的算法没有为任何东西添加书签，所以2将被第二次添加，结果是：7->_6->_5->_4->[2,2]3->_2->[2]1->_0->[]现在可以做两件事：标记哪些集合是为迭代构建的，但这需要额外的工作，或者从高到低迭代。由于所有整数xi都保证为正，我们知道我们不能“升级”向下集合中的集合。如果我们以正确的方式进行整个迭代，那么内存看起来像：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]的副本，如果使用回溯算法就会出现这种情况。对每个元素执行此操作后，每个索引的内存要么是创建子集的方式，其总和对应于索引，要么是null如果无法构造这样的子集。现在你只需查看构造的集合并选择最接近K的集合。我们知道这样的集合最多相差K，因为空集的总和为零，所以K不同。整个故事可以用这个算法来讲述：staticListGetSubset(intvalue,IEnumerablexs){intb=2*value;列表[]cols=新列表[b];cols[0]=新列表();foreach(intxiinxs){for(ints=b-xi-1;s>=0;s--){if(cols[s+xi]==null&&cols[s]!=null){列表cln=newList(cols[s]);cln.Add(xi);cols[s+xi]=cln;}}}for(intd=0;dList方法效率不高：您可以使用头尾列表方法（但不幸的是，.NET库似乎缺少这种方法）。演示（使用csharp交互式shell）：$csharpMonoC#Shell，键入“help；”寻求帮助在下面输入语句。csharp>publicclassFoo{>>publicstaticListGetSubset(intvalue,IEnumerablexs){>intb=2*value;>列表[]cols=新列表[b];>cols[0]=新列表();>foreach(intxiinxs){>for(ints=b-xi-1;s>=0;s--){>if(cols[s+xi]==null&&cols[s]!=null){>Listcln=newList(cols[s]);>cln.Add(xi);>cols[s+xi]=cln;>}>}>}>for(intd=0;dif(cols[value-d]!=null){>returncols[value-d];>}elseif(cols[value+d]!=null){>returncols[value+d];>}>}>returncols[0];>}>}csharp>csharp>int[]items=newint[]{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}如您所见，这些整数无法组成6，但可以得出不超过5的总和这种方法的一个优点是您只需进行一次搜索：您可以多次调用您的方法，首先搜索值K，然后是K+1，然后是K-1，等等。但问题是这将导致在计算昂贵的方法中。以上是C#学习教程：如果没有子集和等于给定值，则返回最接近该值的子集和共享的所有内容。如果对大家有用，需要进一步了解C#学习教程，还望大家多多多多关照——本文收集自网络，不代表立场。如涉及侵权，请点击右侧联系管理员删除。如需转载请注明出处：
