Optimal weights subset sum using backtracking

Question

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.

Answer 1

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:

• It is assumed that 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.
• In order to “prune” the recursion tree, a 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.
• The function runs reasonably fast in my tests for the given array. For a larger number of possible values you probably need a more sophisticated algorithm, such as the dynamic programming approach described in Change-making problem.