0
\$\begingroup\$

I'm solving the "unbounded" variant of the knapsack problem, meaning the repetition of items is allowed. As in the Hackerrank version of the knapsack problem, I am returning the sum nearest to, not exceeding the target.

Some sample calls, with the solutions afterwards ar

unboundedKnapsack(k: 10, arr: [2,3,4]) // 10
unboundedKnapsack(k: 12, arr: [1,6,9]) //12
unboundedKnapsack(k: 9, arr: [3,4,4,4,8]) // 9
unboundedKnapsack(k: 3, arr: [2]) // 2
unboundedKnapsack(k: 13, arr: [3,7,9,11]) //13
unboundedKnapsack(k: 11, arr: [3,7,9]) // 10

I developed a recursive solution, and as below I've added memoization:

func unboundedKnapsack(k: Int, arr: [Int]) -> Int {
    var cache: [[Int]] = Array(repeating: Array(repeating: 0, count: arr.count), count: k)
    return k - knap(k, arr, 0, 0, &cache)
}

func knap(_ target: Int, _ arr: [Int], _ ptr: Int, _ current : Int, _ cache: inout [[Int]]) -> Int {
    // greedy - we either take the current item or  we don't
    if (current > target) {return Int.max}
    if (ptr > arr.count - 1) {return target - current}
    if (current == target) {return target - current}
    if (cache[current][ptr] != 0) {return cache[current][ptr]}
    let result = min(
        // take the current and move pointer
        knap(target, arr, ptr + 1, current + arr[ptr], &cache)
        ,
        // take the current and leave the pointer so we can take more
        knap(target, arr, ptr, current + arr[ptr], &cache),
        // do not take the current and move pointer
        knap(target, arr, ptr + 1, current, &cache)
    )
    cache[current][ptr] = result
    return result
}

I haven't been able to test all inputs for my solution, so I wanted comments on how this particular approach could be improved (using my memoization as shown rather than changing the approach).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.