Skip to content

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
JYK801 opened this issue Nov 24, 2021 · 1 comment
Open

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

JYK801 opened this issue Nov 24, 2021 · 1 comment

Comments

@JYK801
Copy link

JYK801 commented Nov 24, 2021

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

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

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
Copy link
Collaborator

likejazz commented Jan 9, 2022 •
edited
Loading

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@likejazz @JYK801