首页 文章

子集和问题的有趣变化

提问于
浏览
1

一位朋友从工作中向我展示了一个有趣的子集和问题变体:

给定S的正整数,大小为n,以及整数a和K,是否存在包含 exactly a elements 的子集R(集合S),其总和等于K?

他声称这可以用时间复杂度O(nka)来完成,我无法想出一个能够实现这个运行时间的动态编程算法 . 可以吗?

2 回答

  • 3

    如果k和a足够小就可以完成,这样我们就可以声明一个数组

    bool found[a][k]
    

    您将迭代S中的每个值并迭代 found 数组中的每个状态以获得新状态 .

    比方说,对于a = 1和k = 7的索引,以及S的当前值为7,

    如果找到[1] [7]是真的,那么你也可以确定找到[2] [14]也是如此 .

    当迭代结束时,您需要做的就是检查[a] [k]是否为真 .

  • 3

    设S = {s1,\ ldots,sn}

    如果有可能在s1,\ ldots,sj中找到总和为K的元素,则设P(j,K,a)为真 .

    然后P(j,K,a)= P(j-1,K-sj,a-1)或P(j,K,a)(需要sj或者不需要sj) .

    该算法包括用1填充尺寸为n的3-D表.1每个条目需要恒定的时间来填充,因此时间(和空间)复杂度为O(nKa)

相关问题