我目前正在研究一种数学优化问题的算法,并需要处理以下情况。
在许多情况下,算法需要决定哪个子集S ⊂ N在这种情况下最好。
N = { 0, 1, 2, ..., 126, 127 }
|S| ∈ { 0, 1, 2, 3, 4, 5 } (子集大小在0到5之间)
这给出了265,982,833个可能的子集。(binom(128, 5) + binom(128, 4) + ... + binom(128, 0))
如果我预先计算所有可能的子集并将它们存储在一个数组中,那么这个数组将有265,982,833个条目,并且内存占用约为1.27 GB,没有任何优化和子集的朴素存储方式。
在这种情况下,当算法需要知道索引i中特定子集中的元素时,只需要进行表查找。但是巨大的内存需求是不可接受的。
因此,我的问题基本上是是否有人可以想出一种算法,以有效地计算基于索引i的子集中的元素,而无需预先计算数组。
编辑包括样本:
lookupTable[0] = {}
lookupTable[1] = {0}
...
lookupTable[127] = {126}
lookupTable[128] = {127}
lookupTable[129] = {0, 1}
lookupTable[130] = {0, 2}
...
lookupTable[265982832] = {123, 124, 125, 126, 127}