在 Swift 中使用回溯算法平衡权重

Question

我正在尝试使用回溯算法实现解决方案。

我有一些权重 [1,2,7,10,20,70,100,200,700...] 我想 return 给定输入后的权重/

例如输入 => 12 应该 return [2,10] 例如输入 => 8 应该 return [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 //currentValue 现在是 20
1+2+7 // 仍然无解获取最后移除的元素并移除当前最后一个元素
1+2+10 // 正确的权重

我希望你能帮助我，我解释一下我做错了什么。

Answer 1

这是一种解决方案。反向迭代权重。如果权重小于或等于当前总和，则使用权重。

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

Answer 2

不知道你是怎么设置权重的。但请考虑：

[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

在 Swift 中使用回溯算法平衡权重

Balance weights using backtracking algorithm in Swift

algorithm

backtracking

swift