633page knapsack문제(dp) 제안드립니다

[JYK801]

안녕하세요. 책덕분에 도움을 많이 받고 있습니다. 좋은 책 써주셔서 감사드립니다.

개인적으로 이 부분 코드분석할때 가독성이 떨어지는것 같아서 다음 코드를 제 방법대로 바꿔보았습니다.
한번 참고해주시면 감사드리겠습니다.

def zero_one_knapsack(cargo):
capacity = 15
pack = []

for i in range(len(cargo) + 1):
    pack.append([])
    for c in range(capacity + 1):          
        if i == 0 or c == 0:
            pack[i].append(0)
        elif cargo[i - 1][1] <= c:
            pack[i].append(
                max(
                    cargo[i - 1][0] + pack[i - 1][c - cargo[i - 1][1]],
                    pack[i - 1][c]
                ))
        else:
            pack[i].append(pack[i - 1][c])

return pack[-1][-1]

cargo = [
(4, 12),
(2, 1),
(10, 4),
(1, 1),
(2, 2),
]

print(zero_one_knapsack(cargo))

---

def zero_one_knapsack(cargo_price, cargo_weight):
capacity = 15
total_price = []

for i in range(len(cargo_price)):
    total_price.append([])
    for weight in range(capacity + 1):          
        if i == 0 or weight == 0:
            total_price[i].append(0)
        elif cargo_weight[i] <= weight:
            total_price[i].append(
                max(
                    cargo_price[i] + total_price[i - 1][weight - cargo_weight[i]],
                    total_price[i - 1][weight]
                ))
        else:
            total_price[i].append(total_price[i - 1][weight])

return total_price[-1][-1]

cargo_price = [0, 4, 2, 10, 1, 2] # cargo[i-1]을 cargo[i]으로 바꾸기 위해 0부터 시작
cargo_weight = [0, 12, 1, 4, 1, 2]

print(zero_one_knapsack(cargo_price, cargo_weight))

[likejazz]

좋은 제안 감사드립니다. 그런데, 2차원 배열로 풀이하는 DP 풀이를 인덱스도 1로 바꾸고, 별도 변수로 정의하게 되면 기존에 DP에 능숙한 분들은 오히려 혼란을 줄 수 있을거 같습니다. 저 풀이가 모든 DP 풀이에 적용될 수 있는 것도 아니기 때문에 임의로 저런식으로 추상화 하는게 과연 옳은 방식인지는 좀 더 고민이 필요할거 같네요.