子集总和Swift [英] Subset sum Swift
问题描述
我想使用动态编程从给定数组中获取所有子集的总和。
I want to use dynamic programming to get the sum of all subsets from a given array.
subsets([1,2,3]) = 24
Since the subsets are {1}{2}{3}{1,2}{2,3}{1,3}{1,2,3}
我正在尝试计算= 6
的子集([1,2]) 5
I'm trying to calculate subsets([1,2]) which = 6 My implementation below gets 5
func subsets(_ arr: [Int]) -> Int {
var mem = Array(repeating: 0, count: arr.count)
return subsetsRecursive(arr, 0, &mem)
}
// correct result, but too slow so requires memorization
func subsetsRecursive(_ arr: [Int], _ ptr: Int, _ memo : inout [Int]) -> Int {
if (ptr > arr.count - 1) {return 0}
if memo[ptr] != 0 {return memo[ptr]}
// either take the next number, or don't
let res = (
subsetsRecursive(arr, ptr + 1, &memo) + arr[ptr]
+
subsetsRecursive(arr, ptr + 1, &memo)
)
memo[ptr] = res
return res
}
需要纠正什么才能得到正确的答案?这里的方法很重要,它不是家庭作业,而是我对动态编程的自学(我可以找到其他方法,但是想了解这种方法或为什么它不可能)。
What needs to be corrected to get the right answers? The approach here is important, it is not homework but is my self-study about dynamic programming (I can find other approaches for this, but want to understand this approach or why it is not possible).
推荐答案
您的方法的问题在于,递归步骤未将当前元素<$ c $的多少个子集考虑在内c> arr [ptr] 可以组合。例如, subsets([1,2])
计算子集{1,2}和{2}的总和,但忽略子集{1}。
The problem with your approach is that the recursion step does not take into account with how many subsets the current element arr[ptr]
can be combined. For example, subsets([1,2])
computes the sum of the subsets {1, 2} and {2}, but omits the subset {1}.
动态编程方法的一种可能的解决方法是不仅记住总和,还要记住从某个位置开始的所有子集的 count :
A possible fix for the dynamic programming approach would be to remember not only the sum, but also the count of all subsets starting at a certain position:
func subsets(_ arr: [Int]) -> Int {
var mem = Array(repeating: (sum: 0, count: 0), count: arr.count)
return subsetsRecursive(arr, 0, &mem).sum
}
func subsetsRecursive(_ arr: [Int], _ ptr: Int, _ memo : inout [(sum: Int, count: Int)]) -> (sum: Int, count: Int) {
if (ptr > arr.count - 1) { return (sum: 0, count: 1) }
if memo[ptr].sum != 0 { return memo[ptr] }
let res = subsetsRecursive(arr, ptr + 1, &memo)
memo[ptr] = (2 * res.sum + arr[ptr] * res.count, 2 * res.count)
return memo[ptr]
}
示例:
print(subsets([1, 2])) // 6
print(subsets([1, 2, 3])) // 24
这可以进一步简化,但希望能回答您的问题紧迫的问题。
This can be simplified further, but hopefully answers your immediate question.
迭代解决方案是
func subsetsum(_ arr: [Int]) -> Int {
var sum = 0
var count = 1
for elem in arr {
sum = 2 * sum + count * elem
count = 2 * count
}
return sum
}
可以简写为
func subsetsum(_ arr: [Int]) -> Int {
return arr.reduce((sum: 0, count: 1)) {
(2 * $0.sum + $0.count * $1, 2 * $0.count )
}.sum
}
n个数组元素中的每一个都可以位于2 n 个子集中的2 n-1 中:
func subsetsum(_ arr: [Int]) -> Int {
return arr.reduce(0, +) * (1 << (arr.count - 1))
}
这篇关于子集总和Swift的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!