我正在尝试解决一个问题。我有一些重量。 [2,7,20,70,200,700]
在给定输入后,例如 1507
,它应该返回这些权重的最佳组合。在本例中为 [700,200,200,200,200,7]
。不幸的是,我的算法返回了 [700, 700, 70, 20, 7, 2, 2, 2, 2, 2]
。当我说最佳时,我的意思是我的算法应该使用尽可能少的权重。
func solve(_ targetValue: Int, weights: inout [Int]) -> [Int] {
// The used weights to store
var usedWeights: [Int] = []
// The current total value for the calculation
var total = targetValue
// If target value is 0 add it to the array and just return it
if targetValue == 0 { usedWeights.append(0); return usedWeights }
// Loop through the weights
for weight in weights.reversed() {
while weight <= total {
total -= weight
usedWeights.append(weight)
}
} // If still weights are not found call the function recursively again but remove the last element before
if total != 0 {
weights.removeLast()
return solve(targetValue, weights: &weights)
}
return usedWeights
}
var newWeights: [Int] = [2,7,20,70,200,700]
print(solve(1507, weights: &newWeights))
我该如何解决这个问题?我究竟做错了什么?重要的是使用回溯来解决它。非常感谢您的帮助。
最佳答案
这是一个可能的递归解决方案:
// Find the shortest combination of (possibly repeating) numbers in `values`
// whose sum is exactly `target`, and whose count is less than `limit`.
// Return `nil` if no such combination exist.
//
// `target` must be non-negative, and `values` an array of positive
// numbers in decreasing order.
//
func solveHelper(target: Int, values: ArraySlice<Int>, limit: Int) -> [Int]? {
if target == 0 {
return [] // Target reached exactly.
}
guard let first = values.first else {
return nil // No values left, target cannot be reached.
}
if target/first >= limit {
return nil // Target cannot be reached with less than `limit` values.
}
var best: [Int]? = nil // Best solution found so far
var bestCount = limit // Number of values in best solution
for n in stride(from: target/first, through: 0, by: -1) {
if let s = solveHelper(target: target - n * first, values: values.dropFirst(), limit: bestCount - n) {
best = s + repeatElement(first, count: n)
bestCount = s.count + n
}
}
return best
}
// Find the shortest combination of (possibly repeating) values in `values`
// whose sum is exactly `target`. Return `nil` if no such combination exist.
//
// `target` must be non-negative, and `values` an array of positive
// numbers.
//
func solve(target: Int, values: [Int]) -> [Int]? {
return solveHelper(target: target, values: ArraySlice(values.sorted(by: >)), limit: Int.max)
}
例子:
print(solve(target: 1507, values: [2, 7, 20, 70, 200, 700]) as Any)
// Optional([7, 200, 200, 200, 200, 700])
print(solve(target: 1507, values: [20, 70, 200, 700]) as Any)
// nil
print(solve(target: 6, values: [1, 3, 4]) as Any)
// Optional([3, 3])
print(solve(target: 0, values: [1, 3, 4]) as Any)
// Optional([])
一些解释:
- 假定
target
是非负的,并且所有values
是积极的。 solve
对数组进行降序排序,并将其作为一个ArraySlice
到递归辅助函数。这有助于避免 元素存储的进一步副本,当values.dropFirst()
传递给递归调用。solveHelper
以最大可能数量开始“贪婪” 第一个(即最大的)值,递归地调用自己 剩余的目标总和和值,然后用更少的值重复该过程 第一个值的副本,跟踪找到的最短解决方案 到目前为止。- 为了“修剪”递归树,传递了一个
limit
到递归调用。例如,如果1507 = 700 + 200 + 200 + 200 + 200 + 7
已经找到,则不再需要仅对[2, 7, 20, 70]
,那只会给出更长的解决方案。 - 该函数在我对给定数组的测试中运行得相当快。 对于更多的可能值,您可能需要更多 复杂的算法,例如动态规划方法 在 Change-making problem 中描述.
关于swift - 使用回溯的最佳权重子集总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50398745/