Knapsack Problem from Grokking Algorithms

Knapsack.swift

func knapSack(capacity: Int, items: [(weight: Int, value: Int)]) -> Int {
    var grid = Array(repeatElement(Array(repeatElement(0, count: capacity)), count: items.count))
    
    for row in 0 ..< grid.count {
        for column in 0 ..< capacity {
            let item = items[row]
            let maxWeight = column + 1
            let previousMax = row >= 1 ? grid[row - 1][column] : 0
            
            if item.weight <= maxWeight {
                var current = item.value
                
                if item.weight < maxWeight && row >= 1 {
                    current += grid[row - 1][maxWeight - item.weight - 1]
                }
                
                grid[row][column] = max(current, previousMax)
            } else if row > 0 {
                grid[row][column] = previousMax
            }
        }
        print(grid)
    }
    
    // Bottom-right corner == Maximum possible value
    return grid[items.count - 1][capacity - 1]
}

// Stereo, Laptop, Guitar
knapSack(capacity: 4, items: [(weight: 4, value: 3000), (weight: 3, value: 2000), (weight: 1, value: 1500)])

// Add iPhone
knapSack(capacity: 4, items: [(weight: 4, value: 3000), (weight: 3, value: 2000), (weight: 1, value: 1500), (weight: 1, value: 2000)])