使用回溯法求解最优权重子集和

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))

我应该怎么解决这个问题？我做错了什么吗？重要的是使用回溯法来解决它。非常感谢你的帮助。

- BilalReffas

---

FYI - 您检查1、3和5是不必要的。此外，这些权重可能会被传递进来。 - rmaddy

去掉那些检查。你是否有这些权重并不重要。对于许多其他值，您也没有相应的权重。 - rmaddy

但是如果我不检查它，它会使用很多权重。 - BilalReffas

这基本上就是零钱兑换问题（https://en.wikipedia.org/wiki/Change-making_problem）吧？ - AlexQueue

是的，看起来是一样的，我只想用回溯法解决它 @AlexQueue - BilalReffas

Answer 1

以下是可能的递归解决方案：

以下是可能的递归解决方案：

// 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]中的值进行求和，因为那只会得到更长的解决方案。
• 在我的测试中，该函数以合理的速度运行给定的数组。对于更多可能值的情况，您可能需要更复杂的算法，例如找零问题中描述的动态规划方法。

- Martin R

---

非常感谢你，马丁。我也使用了动态规划解决了它，但我的解决方案比你的慢得多。同样感谢你的解释。 - BilalReffas

@martin-r 有没有非重复的解决方案？ - Соёмбо Бат-Эрдэнэ