盘锦市政建设集团网站,wordpress熊掌号自动推送,企业网站开发的公司,价格对比网站开发减治法在生成组合对象问题中的应用
生成子集问题#xff1a;经典的背包问题就是求解一个最优子集的问题#xff0c;这里我们来讨论一个更简单的问题。对于任意一个集合来说#xff0c;它都存在2^n个子集#xff08;一个集合所有的子集集合称为幂集#xff09;。
1…减治法在生成组合对象问题中的应用
生成子集问题经典的背包问题就是求解一个最优子集的问题这里我们来讨论一个更简单的问题。对于任意一个集合来说它都存在2^n个子集一个集合所有的子集集合称为幂集。
1简单递归实现 import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {ListInteger list new ArrayList();list.add(1);list.add(2);list.add(3);ListInteger li new ArrayList();f(0, list, li);}public static void f(int i, List list, List li) {if (i (list.size() - 1)) {System.out.println(li);} else {li.add(list.get(i));// 左加f(i 1, list, li);li.remove(list.get(i)); // 右去f(i 1, list, li);}}} 上面这个算法简单实用但是习惯上来说我们更喜欢严格的升序排列而不是这种混乱的情况。这里引入挤压序的概念集合内按字典序顺序排列集合与集合之间按照元素个数严格增加一种序列。
二进制反射格雷码这种算法得到的序列不仅是挤压序而且还是一种最小变化法。下面的算法是使用了数学公式实现的所以代码量很少既然有数学公式何乐而不为呢难道要像NP问题一样没有公式才好吗算法的“投机取巧”也在能直接利用数学公式上。 import java.util.Scanner;public class Main {public void getGrayCode(int bitNum){for(int i 0; i (int)Math.pow(2, bitNum); i){int grayCode (i 1) ^ i;System.out.println(numBinary(grayCode, bitNum));}}public String numBinary(int num, int bitNum){String ret ;for(int i bitNum-1; i 0; i--){ret (num i) 1;}return ret;}public static void main(String[] args) {Main test new Main();Scanner in new Scanner(System.in);int n in.nextInt();test.getGrayCode(n);}
}
