使用动态规划来找到其和最接近给定数字M的数字的子集 [英] Use dynamic programming to find a subset of numbers whose sum is closest to given number M

问题描述

给定由n个正整数组成的集合A，a1，a2，...A3和另一个正整数M，我要找出A的一个子集，它的和最接近于M。换句话说，我要找到A的一个子集A‘，使其绝对值|M-􀀀Σa∈A’|最小化，其中[Σa∈A‘a]是A’的个数的总和。我只需要返回解决方案子集A‘的元素之和，而不报告实际的子集A’。

例如，如果A为{1，4，7，12}，M=15，则解的子集为A‘={4，12}，因此算法只需返回4+12=16作为答案。

问题的动态规划算法应在 O(NK)最坏情况下的时间，其中K是A的所有数的和。

推荐答案

构造一个大小为n*K的动态规划表，其中

D[i][j] = Can you get sum j using the first i elements ?

您可以使用的递归关系是：D[i][j] = D[i-1][j-a[i]] OR D[i-1][j]如果您认为第i个元素可以添加或保留，则可以推导出此关系。

时间复杂度：O(NK)，其中K=所有元素的和

最后，您迭代您可以得到的所有可能和，即，当j=1..K时，D[n][j]将是您的答案。

这篇关于使用动态规划来找到其和最接近给定数字M的数字的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！