动态编程问题

Question

我正在寻找关于动态编程问题的一些指示.我找不到任何有关如何解决此类问题的相关信息.我知道如何使用动态编程解决的唯一问题是当我有两个序列并创建这些序列的矩阵时.但我不知道如何将其应用于以下问题......

如果我有一个集合A = {7,11,33,71,111}和一个数字B.那么作为A的子集的C包含来自A的元素,它构建了和B.

例:

A = {7,11,33,71,111}
If B = 18, then C = {7,11} (because 7+11 = 18)

If B = 3, then there is no solution

感谢这里的任何帮助,我只是不知道在解决这些问题时如何思考.我也找不到任何一般方法,只有基因序列的一些例子和类似的东西.

Answer 1

动态规划是一类广泛的解决方案,其中部分解决方案保留在某个结构中,以便下一次迭代构建,而不是一遍又一遍地重新计算中间结果.

如果我采用动态方法解决这个特定问题,我可能会保留一个运行列表,其中包含上一步中可计算的每个总和,以及用于计算该总和的集合.

因此,例如我的工作集将包含的第一次迭代{null, 7},然后我将添加11到该集合中的所有内容以及集合本身(让我们暂时假装null+11=11).现在我的工作集将包含{null, 7, 11, 18}.对于集合中的每个值,我会跟踪我是如何得到该结果的:因此7映射到原始集合{7}并18映射到原始集合{7,11}.当A)生成目标值或B)原始集合耗尽而没有找到值时,迭代将结束.你可以用一个有序集来优化负面情况,但我会留意你.

解决这个问题的方法不止一种.这是一个动态的解决方案,因为它需要构建一组2^(size of set)成员,所以效率不高.但是一般方法对应于创建动态编程来解决的问题.