목록백준 12865 (1)

시작이 반

[백준] 12865번(python 파이썬)

knapsack알고리즘 문제이다. 1. 배낭에 물건을 넣는다. - 물건을 넣기전 상태에서 (가방 무게 - 해당 물건 무게)의 가치 + 해당 물건 가치 2. 배낭에 물건을 넣지 않는다. - 이전 값을 그대로 사용한다. ex) 물건 개수 : 4 가방에 들어갈 수있는 최대 무게 : 7 1번 물건 : 6 13 2번 물건 : 4 8 3번 물건 : 3 6 4번 물건 : 5 12 dp[i][j] 1. 물건을 넣는다 : dp[i-1][j - 해당 물건 무게] + 해당 물건 가치 2. 물건을 넣지 않는다 : dp[i-1][j] 1, 2중 최대값을 넣는다. 가방무게 물건 0 1 2 3 4 5 6 7 1번 물건 0 0 0 0 0 0 13 13 2번 물건 0 0 0 0 8 8 13 13 3번 물건 0 0 0 6 8 8 13 ..
알고리즘/백준 2021. 2. 26. 21:49
이전 Prev 1 Next 다음