相关疑难解决方法(0)

我正在研究这个问题:

该子集和问题需要输入一个组X = {x1, x2 ,…, xn}的n整数和另一个整数K.问题是,以检查是否存在一个子集X'的X,它的元素之和为K,并发现该子集,如果有任何.例如,如果X = {5, 3, 11, 8, 2}和K = 16那么答案是YES,因为该子集X' = {5, 11}具有的总和16.实现Subset Sum的算法,其运行时间至少为O(nK).

注意复杂性O(nK).我认为动态编程可能有所帮助.

我找到了一个指数时间算法,但它没有帮助.

有人可以帮我解决这个问题吗？

我有一个代码,通过背包算法计算最佳值(bin packing NP-hard problem):

int Knapsack::knapsack(std::vector<Item>& items, int W)
{
    size_t n = items.size();
    std::vector<std::vector<int> > dp(W + 1, std::vector<int>(n + 1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for ( int w = 1; w <= W; w++)
        {
            if (items[j-1].getWeight() <= w)
            {
                dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight());
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }
    return dp[W][n];
}

另外,我需要显示包含在内的元素.我想创建一个数组,添加一个元素.所以问题在于添加这个添加的步骤,或者可能还有其他更有效的方法吗？

问题:我希望能够了解为我提供最佳解决方案的项目,而不仅仅是最佳解决方案的价值.

PS.对不起我的英语,这不是我的母语.