[Swift] 동적프로그래밍 - 배낭채우기 문제를 Swift로 구현해보자

import Foundation
 
typealias ItemTuple = (name:String,size:Int,value:Int)
 
 
// 최적의 물건들과 가치를 리턴해준다
func getBestItemsAndValue(bagSize:Int,itemTupleArray:[ItemTuple]) -> (Int,String){
    
    //size를 인덱스 겸 진짜 사이즈로 쓰고 싶어서 열을 하나 더 늘림 ..! 0번 열은 안씀
    var grid:[[Int]] = Array(repeating: Array(repeating: 0, count: bagSize+1), count: itemTupleArray.count)
    
    var gridItems:[[String]] = Array(repeating: Array(repeating: "", count: bagSize+1), count: itemTupleArray.count)
    
    //첫번째 행은 자기자신만 넣을 수 있음
    for size in 1...bagSize{
        
        if size < itemTupleArray[0].size{
      
        } else{
            grid[0][size] = itemTupleArray[0].value
            gridItems[0][size] = itemTupleArray[0].name
        }
    }
 
    
    // 두번째 행부터
    for i in 1..<itemTupleArray.count{
        
        for size in 1...bagSize{
            
            let lastValue = grid[i-1][size]
            let lastNames = gridItems[i-1][size]
            
            // 아직 이 아이템이 들어갈 자리가 없으면 예전 값
            if size < itemTupleArray[i].size{
                
                grid[i][size] = lastValue
                gridItems[i][size] = lastNames
 
                continue
            }
            
            
            let newValue = itemTupleArray[i].value + grid[i-1][size-itemTupleArray[i].size]
            let newNames = itemTupleArray[i].name + " + " + gridItems[i-1][size-itemTupleArray[i].size]
            
            
            // 해당 사이즈에 대해 지금까지의 최적의 값보다 현재 물건 + 남은 사이즈가치가 더 크면 갱신시켜준다
            if lastValue < newValue{
                grid[i][size] = newValue
                gridItems[i][size] = newNames
            } else{
                grid[i][size] = lastValue
                gridItems[i][size] = lastNames
            }
 
        }
    }
    
    let maxValue = grid[itemTupleArray.count-1][bagSize]
    let maxItems = gridItems[itemTupleArray.count-1][bagSize]
    
    return (maxValue,maxItems)
}
 
 
 
 
// ex1 - 가방의 무게가 4이고 다음과 같은 아이템들이 있을때, 배낭에 담아야할 최적의 물건들과 그 가치는?
let tuple1:ItemTuple = ("기타",1,1500)
let tuple2:ItemTuple = ("노트북",3,2000)
let tuple3:ItemTuple = ("스테레오",4,3000)
 
print(getBestItemsAndValue(bagSize: 4, itemTupleArray: [tuple1,tuple2,tuple3]))
//(3500, "노트북 + 기타")
 
 
// ex2 - 가방의 무게가 6이고 다음과 같은 아이템들이 있을때, 배낭에 담아야할 최적의 물건들과 그 가치는?
let tuple4:ItemTuple = ("물",3,10)
let tuple5:ItemTuple = ("책",1,3)
let tuple6:ItemTuple = ("음식",2,9)
let tuple7:ItemTuple = ("자켓",2,5)
let tuple8:ItemTuple = ("카메라",1,6)
 
print(getBestItemsAndValue(bagSize: 6, itemTupleArray: [tuple4,tuple5,tuple6,tuple7,tuple8]))
//(25, "카메라 + 음식 + 물")