使用回溯的最佳权重子集和

Question

我正在努力解决问题.我有一些重量.[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))

我怎样才能解决这个问题？我究竟做错了什么？重要的是使用回溯来解决它.我非常感谢你的帮助.

Answer 1

这是一个可能的递归解决方案：

\n\n

// Find the shortest combination of (possibly repeating) numbers in `values`\n// whose sum is exactly `target`, and whose count is less than `limit`.\n// Return `nil` if no such combination exist.\n//\n// `target` must be non-negative, and `values` an array of positive\n// numbers in decreasing order.\n//\nfunc solveHelper(target: Int, values: ArraySlice<Int>, limit: Int) -> [Int]? {\n    if target == 0 {\n        return [] // Target reached exactly.\n    }\n    guard let first = values.first else {\n        return nil // No values left, target cannot be reached.\n    }\n    if target/first >= limit {\n        return nil // Target cannot be reached with less than `limit` values.\n    }\n\n    var best: [Int]? = nil   // Best solution found so far\n    var bestCount = limit // Number of values in best solution\n\n    for n in stride(from: target/first, through: 0, by: -1) {\n        if let s = solveHelper(target: target - n * first, values: values.dropFirst(), limit: bestCount - n) {\n            best = s + repeatElement(first, count: n)\n            bestCount = s.count + n\n        }\n    }\n\n    return best\n}\n\n// Find the shortest combination of (possibly repeating) values in `values`\n// whose sum is exactly `target`. Return `nil` if no such combination exist.\n//\n// `target` must be non-negative, and `values` an array of positive\n// numbers.\n//\nfunc solve(target: Int, values: [Int]) -> [Int]? {\n    return solveHelper(target: target, values: ArraySlice(values.sorted(by: >)), limit: Int.max)\n}\n

\n\n

例子：

\n\n

print(solve(target: 1507, values: [2, 7, 20, 70, 200, 700]) as Any)\n// Optional([7, 200, 200, 200, 200, 700])\n\nprint(solve(target: 1507, values: [20, 70, 200, 700]) as Any)\n// nil\n\nprint(solve(target: 6, values: [1, 3, 4]) as Any)\n// Optional([3, 3])\n\nprint(solve(target: 0, values: [1, 3, 4]) as Any)\n// Optional([])\n

\n\n

一些解释：

\n\n

\n
• 假设target是非负的并且所有values都是正的。
\n
• solve按降序对数组进行排序，并将其作为\n 传递ArraySlice给递归辅助函数。这有助于避免元素存储的进一步副本，当values.dropFirst()当传递给递归调用
\n
• solveHelper以最大可能数量的第一个（即最大）值开始 \xe2\x80\x9cgreedy\xe2\x80\x9d，递归调用自身以获取\n剩余的目标总和和值，然后使用较少的\n副本重复该过程第一个值，跟踪迄今为止找到的最短解决方案。
\n
• 为了 \xe2\x80\x9cprune\xe2\x80\x9d 递归树， alimit被传递\n到递归调用。例如，如果1507 = 700 + 200 + 200 + 200 + 200 + 7已经找到，则不再需要仅对中的值求和[2, 7, 20, 70]，这只会给出更长的解决方案。
\n
• 在我对给定数组的测试中，该函数运行得相当快。\n对于大量可能的值，您可能需要\n更复杂的算法，例如更改问题中描述的\n动态编程方法。
\n

\n