给定一个由 n 个正整数 a1, a2,... a3 和另一个正整数 M 组成的集合 A，我将找到 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] = 你能使用前 i 个元素求和 j 吗？
您可以使用的递归关系是:D[i][j] = D[i-1][j-a[i]] OR D[i-1][j] 这个关系如果认为第i个元素可以添加或留下，则可以导出。
时间复杂度:O(nK)，其中 K=所有元素的总和
最后，迭代可以获得的全部可能总和，即 D[n][j]，j=1..K。最接近 M 的就是您的答案。
关于dynamic-programming - 使用动态规划查找总和最接近给定数字 M 的数字子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33717186/