# Swift Knapsack problem using bottom-down (memoization) approach

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
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).