# 使用栈的记忆化搜索来加速子集和算法

2020/12/01 20:53

public class SubSet {

private List<Integer> list = new ArrayList<>();   //用于存放求取子集中的元素
@Getter
private List<Integer> res = new ArrayList<>();

//求取数组列表中元素和
public int getSum(List<Integer> list) {
int sum = 0;
for(int i = 0;i < list.size();i++)
sum += list.get(i);
return sum;
}

public void getSubSet(int[] A, int m, int step) {
if (res.size() > 0) {
return;
}
while(step < A.length) {
if (getSum(list) == m) {
if (getSum(res) == 0) {
}
}
step++;
getSubSet(A, m, step);
list.remove(list.size() - 1);   //回溯执行语句，删除列表最后一个元素
}
}

public static void main(String[] args) {
SubSet test = new SubSet();
int[] A = new int[6];
for(int i = 0;i < 6;i++) {
A[i] = i + 1;
}
test.getSubSet(A, 8, 0);
System.out.println(test.getRes());
}
}

[1, 2, 5]

public class SubSet {

private List<Integer> list = new ArrayList<>();   //用于存放求取子集中的元素
@Getter
private List<Integer> res = new ArrayList<>();
private Deque<Integer> deque = new ArrayDeque<>();
private Map<String,Integer> map = new HashMap<>();

//求取数组列表中元素和
public int getSum(List<Integer> list) {
int sum = 0;
for(int i = 0;i < list.size();i++)
sum += list.get(i);
return sum;
}

public void getSubSet(int[] A, int m, int step) {
if (res.size() > 0) {
return;
}
while(step < A.length) {
if (!map.containsKey(deque.toString())) {
int sum = getSum(list);
deque.push(A[step]);
map.put(deque.toString(),sum);
if (sum == m) {
if (getSum(res) == 0) {
}
}
}else {
int sum = map.get(deque.toString()) + A[step];
deque.push(A[step]);
map.put(deque.toString(),sum);
if (sum == m) {
if (getSum(res) == 0) {
}
}
}
step++;
getSubSet(A, m, step);
list.remove(list.size() - 1);   //回溯执行语句，删除列表最后一个元素
deque.pop();
}
}

public static void main(String[] args) {
SubSet test = new SubSet();
int[] A = new int[6];
for(int i = 0;i < 6;i++) {
A[i] = i + 1;
}
test.getSubSet(A, 8, 0);
System.out.println(test.getRes());
}
}

[1, 2, 5]

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text.RegularExpressions;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
private class Oranize
{
public List<decimal> array = new List<decimal>();
public List<decimal> res = new List<decimal>();
public Stack<decimal> stack = new Stack<decimal>();
public Hashtable table = new Hashtable();
public decimal index = 0;

public decimal getSum(List<decimal> list)
{
decimal sum = 0;
for (int i = 0; i < list.Count; i++)
{
sum += list[i];
}
return sum;
}

public String stackValue(Stack<decimal> stack)
{
StringBuilder sb = new StringBuilder();
foreach (decimal s in stack)
{
sb.Append(s.ToString());
}
return sb.ToString();
}

public void org(decimal[] arr,decimal all, int step)
{
if (res.Count > 0)
{
return;
}
while (step < arr.Length)
{
if (!table.ContainsKey(index.ToString()))
{
decimal sum = getSum(array);
stack.Push(index);
if (sum == all)
{
if (getSum(res) == 0)
{
foreach (decimal a in array)
{
}
}
}
}
else
{
decimal sum = 0;
if (stack.Count > 0)
{
sum = Convert.ToDecimal(table[stack.Peek().ToString()]) + arr[step];
}
else
{
sum = Convert.ToDecimal(table["0"]) + arr[step];
}
index++;
stack.Push(index);
if (table.ContainsKey(stack.Peek().ToString()))
{
table.Remove(stack.Peek().ToString());
}
if (sum == all)
{
if (getSum(res) == 0)
{
foreach (decimal a in array)
{
}
}
}
}
step++;
org(arr, all, step);
array.RemoveAt(array.Count - 1);
stack.Pop();
}
}
}
static void Main(string[] args)
{
decimal[] A = new decimal[6];
for (int i = 0; i < 6; i++)
{
A[i] = i + 1;
}
Oranize oranize = new Oranize();
oranize.org(A, 8, 0);

foreach (decimal r in oranize.res)
{
Console.Write(r + ",");
}
}
}
}

        private class RedBlackTreeMap
{
private static bool RED = true;
private static bool BLACK = false;

private class Node
{
public String key;
public decimal value;
public Node left;
public Node right;
public bool color;

public Node(String key,decimal value,Node left,Node right,bool color)
{
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.color = color;
}

public Node(String key): this(key, 0, null, null, RED)
{ }

public Node(String key,decimal value): this(key, value, null, null, RED)
{ }
}

private Node root;
private int size;
public ISet<String> keySet = new HashSet<String>();

public RedBlackTreeMap()
{
root = null;
size = 0;
}

private bool isRed(Node node)
{
if (node == null)
{
return BLACK;
}
return node.color;
}

private Node leftRotate(Node node)
{
Node ret = node.right;
Node retLeft = ret.left;
node.right = retLeft;
ret.left = node;
ret.color = node.color;
node.color = RED;
return ret;
}

private Node rightRotate(Node node)
{
Node ret = node.left;
Node retRight = ret.right;
node.left = retRight;
ret.right = node;
ret.color = node.color;
node.color = RED;
return ret;
}

private void flipColors(Node node)
{
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}

{
}

private Node add(Node node,String key,decimal value)
{
if (node == null)
{
size++;
return new Node(key, value);
}
if (key.CompareTo(node.key) < 0)
{
}else if (key.CompareTo(node.key) > 0)
{
}else
{
node.value = value;
}
if (isRed(node.right) && !isRed(node.left))
{
node = leftRotate(node);
}
if (isRed(node.left) && isRed(node.left.left))
{
node = rightRotate(node);
}
if (isRed(node.left) && isRed(node.right))
{
flipColors(node);
}
return node;
}

public bool contains(String key)
{
return getNode(root, key) != null;
}

public decimal get(String key)
{
Node node = getNode(root, key);
return node == null ? 0 : node.value;
}

public void set(String key,decimal value)
{
Node node = getNode(root, key);
if (node == null)
{
throw new ArgumentException(key + "不存在");
}
node.value = value;
}

public int getSize()
{
return size;
}

public bool isEmpty()
{
return size == 0;
}

private Node getNode(Node node,String key)
{
if (node == null)
{
return null;
}
if (key.CompareTo(node.key) == 0)
{
return node;
}else if (key.CompareTo(node.key) < 0)
{
return getNode(node.left, key);
}else
{
return getNode(node.right, key);
}
}
}

private class HashFind
{
private int[] capacity = {53,97,193,389,769,1543,3079,6151,12289,24593,
49157,98317,196613,393241,786433,1572869,3145739,
6291469,12582917,25165843,50331653,100663319,
201326611,402653189,805306457,1610612741};

//容忍度上界
private static int upperTol = 10;
//容忍度下届
private static int lowerTol = 2;
private int capacityIndex = 0;

private RedBlackTreeMap[] tables;
private int M;
private int size;

public HashFind()
{
this.M = capacity[capacityIndex];
this.size = 0;
tables = new RedBlackTreeMap[M];
for (int i = 0; i < M; i++)
{
tables[i] = new RedBlackTreeMap();
}
}

private int hash(String key)
{
return (key.GetHashCode() & 0x7fffffff) % M;
}

{
RedBlackTreeMap map = tables[hash(key)];
if (map.contains(key))
{
}else
{
size++;
if (size >= upperTol * M && capacityIndex + 1 < capacity.Length)
{
capacityIndex++;
resize(capacity[capacityIndex]);
}
}
}

public bool contains(String key)
{
int index = hash(key);
return tables[index].contains(key);
}

public decimal get(String key)
{
int index = hash(key);
return tables[index].get(key);
}

public void set(String key,decimal value)
{
int index = hash(key);
RedBlackTreeMap map = tables[index];
if(!map.contains(key))
{
throw new ArgumentException(key + "不存在");
}
}

public int getSize()
{
return size;
}

public bool isEmpty()
{
return size == 0;
}

private void resize(int newM)
{
RedBlackTreeMap[] newTables = new RedBlackTreeMap[newM];
for (int i = 0; i < newM; i++)
{
newTables[i] = new RedBlackTreeMap();
}
int oldM = this.M;
this.M = newM;
for (int i = 0; i < oldM; i++)
{
RedBlackTreeMap map = tables[i];
foreach (String key in map.keySet)
{
int index = hash(key);
}
}
this.tables = newTables;
}
}

private class Oranize
{
public List<decimal> array = new List<decimal>();
public List<decimal> res = new List<decimal>();
public Stack<decimal> stack = new Stack<decimal>();
public HashFind table = new HashFind();
public decimal index = 0;

public decimal getSum(List<decimal> list)
{
decimal sum = 0;
for (int i = 0; i < list.Count; i++)
{
sum += list[i];
}
return sum;
}

//public String stackValue(Stack<decimal> stack)
//{
//    StringBuilder sb = new StringBuilder();
//    foreach (decimal s in stack)
//    {
//        sb.Append(s.ToString());
//    }
//    return sb.ToString();
//}

public void org(decimal[] arr, decimal all, int step)
{
if (res.Count > 0)
{
return;
}
while (step < arr.Length)
{
if (!table.contains(index.ToString()))
{
decimal sum = getSum(array);
stack.Push(index);
if (sum == all)
{
if (getSum(res) == 0)
{
foreach (decimal a in array)
{
}
}
}
}
else
{
decimal sum = 0;
if (stack.Count > 0)
{
sum = Convert.ToDecimal(table.get(stack.Peek().ToString())) + arr[step];
}
else
{
sum = Convert.ToDecimal(table.get("0")) + arr[step];
}
index++;
stack.Push(index);
if (!table.contains(stack.Peek().ToString()))
{
}
if (sum == all)
{
if (getSum(res) == 0)
{
foreach (decimal a in array)
{
}
}
}
}
step++;
org(arr, all, step);
array.RemoveAt(array.Count - 1);
stack.Pop();
}
}
}

public class Combine {
private static Map<String,Long> map= new HashMap<>();

/**
* 计算从m个元素中拿出n个元素的组合数
* @param m
* @param n
* @return
*/
private static long comb(int m,int n){
String key= m+","+n;
if(n == 0)
return 1;
if (n == 1)
return m;
if(n > m / 2)
return comb(m,m-n);
if(n > 1){
if(!map.containsKey(key))
map.put(key, comb(m-1,n-1)+comb(m-1,n));
return map.get(key);
}
return -1;
}

public static void main(String[] args) {
long total = 0;
for (int i = 1 ; i <= 4; i++) {
total += comb(4,i);
}
System.out.println(total);
}
}

15

public static void main(String[] args) {
long total = 0;
for (int i = 1 ; i <= 40; i++) {
total += comb(40,i);
}
System.out.println(total);
}

1099511627775

public static void main(String[] args) {
long total = 0;
for (int i = 1 ; i <= 28; i++) {
total += comb(28,i);
}
System.out.println(total);
}

268435455

public static void main(String[] args) {
long total = 0;
for (int i = 1 ; i <= 30; i++) {
total += comb(30,i);
}
System.out.println(total);
}

1073741823

0 评论
0 收藏
0