* @author chenzhuzuo
* @version2011.06.24
* 回溯法求子集和
*
*/
public class SubSum {
/**
* @param args
*/
public static void main(String[] args) {
int a[]= new int []{1,2,3,4,5,6};
getSum(a,6);
}
private static void getSum(int arr[],int sum){
int len= arr.length;
int s[] = new int[len+1];
for(int i=0;i<=len;i++){
s[i]=0;
}
int k=1;
while(k>=1){
s[k]=1;
if(sum==sum(arr,k,s)){
for(int i=1;i<=k;i++){
if(s[i]==1)
System.out.println(arr[i-1]);
}
return;
}
else if(sum>sum(arr,k,s)){
k++;
}else{
s[k]=0;
k++;
}
if(k>len){
while(s[k-1]==1){
s[k-1]=0;
k--;
}
while(s[k-1]==0){
k--;
if(k<1){
System.out.println("result not found");
return;
}
}
s[k-1]=0;
}
}
}
private static int sum(int[] arr, int k,int []s) {
int sum=0;
for(int i=1;i<=k;i++){
if(s[i]==1)
sum+=arr[i-1];
}
return sum;
}
}
分享到:
相关推荐
用回溯法实现子集和问题的完整代码
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解0-1背包问题。 0-1 背包问题描述如下:给定n 种物品和一个背包。物品i的重量是wi,其价值为...
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解装载问题。 装载问题描述如下:有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的...
利用回溯法求子集和(给定sum,求出任意一个满足条件的集合)
本代码大量注释,便于理解。回溯法解决01背包问题,相对于动态规划来说,我们首先得了解问题的解空间,了解解空间的组织结构,最后搜索解空间,其中加入约束条件和限界条件是关键,否则就是穷举了。
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解装载问题。 装载问题描述如下:有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的...
给定N个数,和一个整数M,判定是否可以从N个数中取出若干个数,使它们的和等于M。输出:YES或者NO。把N个数看成一个集合,问题就是从这个集合中选出一个子集,使这个子集满足和是M
试设计一个解子集和问题的回溯法。对于给定的正整数的集合 S={x1,x2,…,xn }S={x1,x2,…,xn }和正整数 c,编程计算 S 的一个子集S1,使得∑x∈S1x=c ∑x∈S1x=c。数据输入:第 1 行有 2 个正整数 n 和 c,n ...
试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解0-1背包问题。 0-1 背包问题描述如下:给定n 种物品和一个背包。物品i的重量是wi,其价值为...
回溯法实现n皇后问题,并输出每种放法的皇后位置
子集和数问题,回溯法实现
本例采用了java编写的图的m着色问题,采用的回溯法,参考:算法设计与分析
回溯法的基本思想、回溯法的递归流程、用回溯法解决问题 的步骤;注意概念:解空间、可行解、约束函数、限界函数。 子集树和排列树的搜索; 皇后问题的回溯算法 * ; Hamilton 回路 * 与旅行商问题的回溯...
回溯法求子集:输入n,输出集合{1,2,…,n}的所有子集(n) 回溯法求子集:输入n,输出集合{1,2,…,n}的所有子集(n)
试设计一个解子集和问题的回溯法。 «编程任务: 对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,编程计算S 的一个子集 S1,使得x∈S1,∑x=c. Input 由文件input.txt 提供输入数据。文件第1 行有2 个正整数...
试设计一个解子集和问题的回溯法。 算法设计:对于给定的正整数的集合S={x1,x2,...,xn}和正整数c,计算S的一个子集S1,使得子集里的元素之和为c。 数据输入:由文件input.txt提供输入数据。文件第1行有2个正整数n和c...
试设计一个解子集和问题的回溯法。 编程任务: 对于给定的正整数的集合S={ 1 x , 2 x ,…, n x }和正整数c,编程计算S 的一个子集S1,使得。 数据输入: 第1 行有2 个正整数n 和c,n 表示S 的大小,c是...
很多人在算法分析中说打印子集很难 我当初用c编写的一个程序,是利用文件的打开,复制存取中间子集来实现了打印所有的子集
给定一个n个整数的集合X={x1,x2....xn}和整数y,找出和等于y的X的子集Y.