Сумма подмножества оптимальных весов с использованием обратного отслеживания

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

Вот возможное рекурсивное решение:

// 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 начинает «жадный» с максимально возможным числом первого (то есть наибольшего) значения, вызововсам рекурсивно для оставшейся целевой суммы и значений, затем повторяет процесс с меньшим количеством копий первого значения, отслеживая самое короткое найденное решение.
• Чтобы «обрезать» дерево рекурсии, a limit передается на рекурсивный вызов.Например, если 1507 = 700 + 200 + 200 + 200 + 200 + 7 уже найдено, то больше нет необходимости суммировать только значения в [2, 7, 20, 70], что дало бы только более длинные решения.
• Функция работает достаточно быстро в моих тестах дляданный массив.Для большего числа возможных значений вам, вероятно, понадобится более сложный алгоритм, такой как подход динамического программирования, описанный в Проблема изменения .