![](https://iknow-base.cdn.bcebos.com/lxb/notice.png)
子集和问题
用pascal的搜索与回溯做,要不超时的!急急急子集和问题Description子集和问题的一个实例为〈S,t〉。其中,S={x1,x2,...,xn}是一个正整数的集合...
用pascal的搜索与回溯做,要不超时的!急急急
子集和问题
Description
子集和问题的一个实例为〈S,t〉。其中,S={x1,x2,...,xn}是一个正整数的集合,c
是一个正整数。子集和问题判定是否存在S的一个子集S1,使得x∈S1,∑x=c.
试设计一个解子集和问题的回溯法。
«编程任务:
对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,编程计算S 的一个子集
S1,使得x∈S1,∑x=c.
Input
由文件input.txt 提供输入数据。文件第1 行有2 个正整数n 和c,n 表示S 的大小,c
是子集和的目标值。接下来的1 行中,有n 个正整数,表示集合S 中的元素。
Output
程序运行结束时,将子集和问题的解输出到文件output.txt中。
当问题无解时,输出“No Solution!”。
Sample Input
5 10
2 2 6 5 4
Sample Output
2 2 6 展开
子集和问题
Description
子集和问题的一个实例为〈S,t〉。其中,S={x1,x2,...,xn}是一个正整数的集合,c
是一个正整数。子集和问题判定是否存在S的一个子集S1,使得x∈S1,∑x=c.
试设计一个解子集和问题的回溯法。
«编程任务:
对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,编程计算S 的一个子集
S1,使得x∈S1,∑x=c.
Input
由文件input.txt 提供输入数据。文件第1 行有2 个正整数n 和c,n 表示S 的大小,c
是子集和的目标值。接下来的1 行中,有n 个正整数,表示集合S 中的元素。
Output
程序运行结束时,将子集和问题的解输出到文件output.txt中。
当问题无解时,输出“No Solution!”。
Sample Input
5 10
2 2 6 5 4
Sample Output
2 2 6 展开
1个回答
推荐于2016-12-01
展开全部
用回溯法解这道题,我本来想修改排列树使之可以求出一个集合的所有子集。但是分析了一下,时间复杂度比求全排列并没有多少减少。所以就直接求出全排列来解除此题。(想通了,求子集应该用子集树来解决)
注:这个题用子集树解更简单,时间复杂度更低。类似于0-1背包的回溯法。
注:这个题用子集树解更简单,时间复杂度更低。类似于0-1背包的回溯法。
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询