Алгоритм SSP минимального подмножества длины k - PullRequest
Новая
       22

Алгоритм SSP минимального подмножества длины k

0 голосов
/ 30 мая 2018

Предположим, что S - это множество с t элементами по модулю n.Действительно, есть 2 ^ t подмножеств любой длины.Проиллюстрируйте программу PARI / GP, которая находит наименьшее подмножество U (с точки зрения длины) отдельных элементов, так что сумма всех элементов в U равна 0 по модулю n.Легко написать программу, которая выполняет поиск с помощью грубой силы, но грубая сила невозможна, когда t и n становятся больше, поэтому была бы признательна за помощь в написании программы, которая не использует грубую силу для решения этого случая суммы подмножества проблема .

Ответы [ 2 ]

0 голосов
/ 30 мая 2018

Я получил этот код от здесь Я не знаю, погода, кажется, работает. 

function getSummingItems(a,t){
  return a.reduce((h,n) => Object.keys(h)
                                 .reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n)))
                                                                                      : m[k].map(sa => sa.concat(n)),m)
                                                                 :  m, h), {0:[[]]})[t];
}
var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20]
    tgt = 42,
    res = [];

console.time("test");
res = getSummingItems(arr,tgt);
console.timeEnd("test");
console.log("found",res.length,"subsequences summing to",tgt);
console.log(JSON.stringify(res));
0 голосов
/ 30 мая 2018

Динамический подход: 

def isSubsetSum(st, n, sm) :

    # The value of subset[i][j] will be
    # true if there is a subset of 
    # set[0..j-1] with sum equal to i
    subset=[[True] * (sm+1)] * (n+1)

    # If sum is 0, then answer is true
    for i in range(0, n+1) :
        subset[i][0] = True

    # If sum is not 0 and set is empty,
    # then answer is false
    for i in range(1, sm + 1) :
        subset[0][i] = False

    # Fill the subset table in botton 
    # up manner
    for i in range(1, n+1) :
        for j in range(1, sm+1) :
            if(j < st[i-1]) :
                subset[i][j] = subset[i-1][j]
            if (j >= st[i-1]) :
                subset[i][j] = subset[i-1][j] or subset[i - 1][j-st[i-1]]

    """uncomment this code to print table
    for i in range(0,n+1) :
        for j in range(0,sm+1) :
            print(subset[i][j],end="")
    print(" ")"""

    return subset[n][sm];
...