Алгоритм сумм подмножеств

Question

Я работаю над этой проблемой:

Задача суммы поднабора принимает в качестве входных данных набор X = {x1, x2 ,…, xn} из n целых чисел и другое целое число K.Проблема состоит в том, чтобы проверить, существует ли подмножество X' из X, элементы которого составляют K, и находит подмножество, если оно есть.Например, если X = {5, 3, 11, 8, 2} и K = 16, то ответом будет YES, поскольку подмножество X' = {5, 11} имеет сумму 16.Реализуйте алгоритм для суммы подмножеств, чье время выполнения составляет не менее O(nK).

Обратите внимание на сложность O(nK).Я думаю, что динамическое программирование может помочь.

Я нашел экспоненциальный алгоритм времени, но он не помогает.

Может кто-нибудь помочь мне решить эту проблему?

Answer 1

пусть M будет суммой всех элементов. Обратите внимание, что K <= M </p>

let m be a Boolean array [0...M]
set all elements of m to be False
m[0]=1
for all numbers in the set let a[i] be the ith number
    for j = M to a[i]
        m[j] = m[j] | m[j-a[i]];

Тогда просто проверьте m [k]

Answer 2

Решение DP с одномерным массивом (здесь важен порядок обработки массива DP).

bool subsetsum_dp(vector<int>& v, int sum)
{
    int n = v.size();
    const int MAX_ELEMENT = 100;
    const int MAX_ELEMENT_VALUE = 1000;
    static int dp[MAX_ELEMENT*MAX_ELEMENT_VALUE + 1]; memset(dp, 0, sizeof(dp));

    dp[0] = 1;

    for (int i = 0; i < n; i++)
    {
        for (int j = MAX_ELEMENT*MAX_ELEMENT_VALUE; j >= 0; j--)
        {
            if (j - v[i] < 0) continue;
            if (dp[j - v[i]]) dp[j] = 1; 
        }
    }

    return dp[sum] ? true : false;
}