使用动态规划找到其和最接近给定数字 M 的数字子集
Use dynamic programming to find a subset of numbers whose sum is closest to given number M
给定一个由 n 个正整数 a1、a2、... a3 和另一个正整数 M 组成的集合 A，我要找到 A 的数字子集，其总和最接近 M。换句话说，我正在尝试找到 A 的子集 A'，使得绝对值 |M - Σ a∈A'|被最小化，其中 [ Σ a∈A' a ] 是 A' 的个数的总和。我只需要return解决方案子集A'的元素之和而不报告实际子集A'。
例如，如果A为{1, 4, 7, 12}，M = 15，则解子集为A' = {4, 12}，因此算法只需要return 4 + 12 = 16 作为答案。
问题的动态规划算法应该运行在
最坏情况下的 O(nK) 时间，其中 K 是 A 所有数字的总和。
您构建了一个大小为 n*K 的动态规划 table，其中
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=所有元素的总和
最后你遍历你能得到的所有可能的总和，即 D[n][j] for j=1..K。哪个最接近 M 就是你的答案。
对于动态算法，我们
- 定义我们要处理的值
这里的一组值其实是一个table.
对于这个问题，我们定义值DP[i , j]作为我们是否可以使用前i个元素得到和j的指标。 （1表示是，0表示否）
这里0<=i<=n，0<=j<=K，其中K是A中所有元素的和
- 定义递归关系
DP[i+1 , j] = 1 , 如果 ( DP[i,j] == 1 || DP[i,j-A[i+1]] ==1)
否则，DP[i+1, j] = 0.
不要忘记首先将 table 初始化为 0。这解决了边界和琐碎的情况。
计算你想要的值
通过自下而上的实现，最终可以填满整个table。
现在，事情变得简单了。你只需要在值为1的table中找出最接近M的值即可。
在这里，只处理DP[n][j]，因为n涵盖了整个集合。找到最接近M的值为1的j。
时间复杂度为 O(kn)，因为你总共迭代了 k*n 次。
给定一个由 n 个正整数 a1、a2、... a3 和另一个正整数 M 组成的集合 A，我要找到 A 的数字子集，其总和最接近 M。换句话说，我正在尝试找到 A 的子集 A'，使得绝对值 |M - Σ a∈A'|被最小化，其中 [ Σ a∈A' a ] 是 A' 的个数的总和。我只需要return解决方案子集A'的元素之和而不报告实际子集A'。
例如，如果A为{1, 4, 7, 12}，M = 15，则解子集为A' = {4, 12}，因此算法只需要return 4 + 12 = 16 作为答案。
问题的动态规划算法应该运行在 最坏情况下的 O(nK) 时间，其中 K 是 A 所有数字的总和。
您构建了一个大小为 n*K 的动态规划 table，其中
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=所有元素的总和
最后你遍历你能得到的所有可能的总和，即 D[n][j] for j=1..K。哪个最接近 M 就是你的答案。
对于动态算法，我们
- 定义我们要处理的值
这里的一组值其实是一个table.
对于这个问题，我们定义值DP[i , j]作为我们是否可以使用前i个元素得到和j的指标。 （1表示是，0表示否）
这里0<=i<=n，0<=j<=K，其中K是A中所有元素的和
- 定义递归关系
DP[i+1 , j] = 1 , 如果 ( DP[i,j] == 1 || DP[i,j-A[i+1]] ==1)
否则，DP[i+1, j] = 0.
不要忘记首先将 table 初始化为 0。这解决了边界和琐碎的情况。
计算你想要的值
通过自下而上的实现，最终可以填满整个table。
现在，事情变得简单了。你只需要在值为1的table中找出最接近M的值即可。
在这里，只处理DP[n][j]，因为n涵盖了整个集合。找到最接近M的值为1的j。
时间复杂度为 O(kn)，因为你总共迭代了 k*n 次。