Балансировка весов с использованием алгоритма возврата в Swift

Question

Я пытаюсь реализовать решение с использованием алгоритма возврата.

У меня есть несколько весов [1,2,7,10,20,70,100,200,700...], и я хочу вернуть веса после заданного ввода /

Например, input => 12 должен вернуть [2,10] Например, input => 8 должен вернуть [1,7]

Кажется, мой код не очень хорошо работает. Он работает только для некоторых входных чисел, таких как 13 или 8

for targetValue in [13] {
    var currentValue = 0
    var usedWeights: [Int] = []
    for weight in weights {
        if targetValue > weight {
            currentValue += weight
            usedWeights.append(weight)
        } else if weight > targetValue {
            let rememberLast = usedWeights.last ?? 0
            usedWeights.remove(at: usedWeights.count-1)
            currentValue -= rememberLast
            if currentValue > targetValue || currentValue < targetValue {
                let last = usedWeights.remove(at: usedWeights.count-1)
                currentValue -= last
                usedWeights.append(rememberLast)
                currentValue -= rememberLast
            print(usedWeights) /// [1, 2, 10] Yeah it work's :) but only for some number ..:(
            }
        }
    }
}

Используемые веса должны быть уникальными.

У меня есть некоторые проблемы с поиском весов.

Вот как работает алгоритм Ввод => 13
1
1 + 2
1 + 2 + 7
1 + 2 + 7 + 10 // текущее значение теперь 20
1 + 2 + 7 // все еще нет решения получить последний удаленный элемент и удалить текущий последний элемент
1 + 2 + 10 // Правильные веса

Надеюсь, вы мне поможете, и я объясню, что я делаю неправильно.

Answer 1

Я не знаю, как вы устанавливаете вес. Но учтите:

[2,3,6,10,20]
and needed = 21

Тогда алгоритм не найдет его (без совпадения), когда очевидно решение: 2 + 3 + 6 + 10

Итак, вы должны рекурсивно вызывать алгоритм поиска, когда он не работает, после удаления из весов первого выбранного вами значения.

Это не очень чисто, но, кажется, работает (в коде, некоторые проблемы на детской площадке)

func searchIt(weightsSearch: [Int], neededSearch: Int) -> (needs: [Int], remainingWeights: [Int], found: Bool) {
    var total = neededSearch // The current working total
    var needs = [Int]() // The resulting weights needed
    var remaining = weightsSearch
    var firstNotYetSelected = true
    var position = weightsSearch.count - 1
    for weight in weightsSearch.reversed() {
        if weight <= total {
            needs.append(weight)
            total -= weight
            if firstNotYetSelected {
                remaining.remove(at : position)
            }
            firstNotYetSelected = false
            position -= 1
        }
    }
return (needs, remaining, total == 0)
}

var needs = [Int]() // The resulting weights needed
var remainingWeights = weights
var foundIt: Bool
repeat {
    (needs, remainingWeights, foundIt) = searchIt(weightsSearch: remainingWeights, neededSearch: needed)
    if foundIt {
        print("Need \(needs) for \(needed)")
        break
    } else {
        print("No match yet for \(needed)")
    }
} while remainingWeights.count >= 1

с тестовым набором

let weights = [2,3,6,10,20] 
let needed = 21 

получаем

No match yet for 21
Need [10, 6, 3, 2] for 21

Если вам нужны ВСЕ решения, замените оператор break на continue.

С тестовым набором

let weights = [2,3,6,10,15,20] 
let needed = 21 

мы получаем 2 решения

No match for 21
No match for 21
Need [15, 6] for 21
Need [10, 6, 3, 2] for 21
No match for 21
No match for 21
No match for 21

Answer 2

Вот одно из решений. Итерация в обратном порядке через веса. Если вес меньше или равен текущей сумме, используйте вес.

let weights = [1,2,7,10,20,70,100,200,700] // the weights you have
let needed = 12 // The total weight you want

var total = needed // The current working total
var needs = [Int]() // The resulting weights needed
for weight in weights.reversed() {
    if weight <= total {
        needs.append(weight)
        total -= weight
    }
}
if total == 0 {
    print("Need \(needs) for \(needed)")
} else {
    print("No match for \(needed)")
}