从论坛里一哥们的回复中摘来的,反正我是受教了。
import java.util.Stack;
public class SubsetCalc {
private int[] a = { 8, 5, 4, 3, 2, 1 };
private int sum = 10;
private Stack<Integer> stack = new Stack<Integer>();
private int stackSum = 0;
private void calc(int from, int to) {
if (stackSum == sum) {
for (Integer i : stack)
System.out.print(i + " ");
System.out.println();
return;
}
for (int i = from; i < to; i++) {
if (stackSum + a[i] <= sum) {
stackSum += stack.push(a[i]);
calc(i + 1, to);
stackSum -= stack.pop();
}
}
}
public void subsets() {
calc(0, a.length);
}
public static void main(String[] args) {
new SubsetCalc().subsets();
}
}
此算法有两种思路在里面。
1.遍历过程得到了所有子集的情况;
2.在1的基础之上得到和为10的子集。
纠正:上面1中所说有误,应是:遍历过程得到了所有和小于等于10的所有子集的情况。
补充:遍历所有子集的情况的代码如下
public class RecursionTest {
private int[] a={8,5,4,3,2,1};
private Stack<Integer> stack=new Stack<Integer>();
private void calc(int from, int to)
{
for(int i=from;i<to;i++)
{
stack.push(a[i]);
calc(i+1,to);
stack.pop();
}
for(Integer i:stack)
{
System.out.print(i+" ");
}
System.out.println();
}
public void subsets()
{
calc(0,a.length);
}
public static void main(String[] args) {
new RecursionTest().subsets();
}
}
分享到:
相关推荐
java实验--求一个集合的子集,非递归实现。
试写一个递归算法实现求一个集合的所有子集。 算法设计: 给定一个非空的集合,用递归算法输出它的所有子集。 数据输入: 由文件input.txt 提供输入数据。文件第1行是集合中的元素个数,第2行是集合的元素序列(元素...
给定一个非空的集合,用递归算法输出它的所有子集。由文件input.txt 提供输入数据。文件第1行是集合中的元素个数,第2行是集合的元素序列(元素之间用空格分隔)。将计算出的所有子集分行输出到文件output.txt中。
该程序实现了子集和问题的递归回溯解法 相信学acm或者算法设计的人都可以参考
交错幂集是一种数学概念,它是由集合的所有子集的交错和构成的集合。具体来说,对于一个集合S,其交错幂集P(S)定义为:P(S) = {x ∈ S^n | x1 ≠ x2, 当 1 ≤ i ≤ n},其中S^n表示S的所有n元子集的集合。 该代码...
求一个集合子集的算法示例, 用两种方法解,一种是基于回溯的递归求解,一种基于位域映射.
求集合的所有子集问题,提供的全部代码。 使用递归算法!
用回溯法实现子集和问题的完整代码
找到一个给定集合的所有子集,一个简单的小程序
回溯法的基本思想、回溯法的递归流程、用回溯法解决问题 的步骤;... 定和子集问题的回溯算法; 最大团问题的回溯算法; 0/1 背包问题的回溯算法 * ; 图的顶点着色问题的回溯算法 ** 。
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
使用递归回溯实现子集和问题。 作为提供实现SubsetSum类包中包含的io.gitbub.thehappybug.Algorithms 。 编译 可以使用make工具编译项目: $ make javac io/github/thehappybug/Algorithms/SubsetSum.java 跑步 ...
C#,子集和问题(Subset Sum Problem)的算法与源代码 1 子集和问题(Subset Sum Problem) 给定一组非负整数和一个值和,确定给定集合中是否存在和等于给定和的子集。 示例: 输入:set[]={3,34,4,12,5,2},...
如果 0 表示未选择,1 表示已选择,则基于 0 和 1 的数组打印字符串将为我们提供给定字符串的所有可能子集。 由于每个字母都可以被选中或拒绝,因此每个字母都有 2 种可能性。 因此,如果该算法是 O(2^n),则复杂度...
书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。此书还介绍了对强连通...
熟悉线和队列设计,使用栈或队列解决算法设计问题,理解栈和队列的作用:掌握递归算法设计方法。栈和队列的设计和应用;递归算法设计。需要使用栈或队列的算法通常较复杂,理解对于什么应用问题需要使用栈或队列,...
11 .3 .1 装箱问题 11 .3 .2 子集和问题 11 .4 实验项目— — —TSP 问题的近似算法 阅读材料— — —量子密码技术 习题 11 第 12 章 计算复杂性理论 12 .1 计算模型 12 .1 .1 图灵机的基本模型 12 .1 .2 k 带图灵机...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书将严谨性和全面性融为一体,深入讨论各类算法,并着力使这些算法的设计和分析能为各个层次的读者接受。全书各章自成体系,可以作为独立的学习单元;算法以英语和伪代码的形式描述,具备初步程序设计经验的人就能...