I'm trying to solve a problem. I have some weights. [2,7,20,70,200,700]
After a given input, for example 1507, it should return the optimal combination of those weights. Which in this case would be [700,200,200,200,200,7]. Unfortunately my algorithm is returning [700, 700, 70, 20, 7, 2, 2, 2, 2, 2]. When I say optimal I mean that my algorithm should use the fewest number of weights as possible.
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))
How can I fix this? What am I doing wrong? The important thing is to solve it using backtracking. I really appreciate your help.
Here is a possible recursive solution:
// 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)
}
Examples:
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([])
Some explanations:
target is non-negative and that all values
are positive.solve sorts the array in descending order and passes it as an
ArraySlice to the recursive helper function. This helps to avoid
further copies of the element storage, when values.dropFirst()
is passed to the recursive call.solveHelper starts “greedy” with the maximal possible number of
the first (i.e. largest) value, calls itself recursively for the
remaining target sum and values, then repeats the process with less
copies of the first value, keeping track of the shortest solution found
so far.limit is passed
to the recursive call. As an example, if 1507 = 700 + 200 + 200 + 200 + 200 + 7 has already been found then there is no need anymore to sum only values in [2, 7, 20, 70], that would only give longer solutions.