백준 12865번 (냅색 알고리즘과 이차원 리스트 초기화)

여러가지 경우의 수로 주어진 무게 안에서 최고의 가치를 끌어내는 알고리즘을 만들어야만 했다.

처음에는 두개의 리스트나 딕셔너리로 모든 경우를 조합해서 그 중 무게가 허용되는 것 중에서 최고의 가치

를 가지는 조합을 뽑는 알고리즘을 만들어보려 했으나 실패했다.

그리고 이 문제는 냅색 알고리즘으로 풀어낼 수 있는 것을 알아냈다.

		0	1	2	3	4	5	6	7
weight	value
6	13		0	0	0	0	0	13	13
4	8		0	0	0	8	8	13	13
3	6		0	0	6	8	8	13	14
5	12		0	0	6	8	12	13	14

list[i][j] = list(value+knapsack[i-1][j-weight], list[i-1][j])

냅색 알고리즘이란 물건의 수 N과 허용된 무게 K로 이루어진 리스트를 돌며 (이 물건을 넣었을 경우의 지금까지 알아낸 최고 가치)와 (이 물건을 넣지 않았을 경우의 지금까지 알아낸 최고 가치)를 계속 비교하며 결국 [N][K]에 도달하면 최고 가치를 얻게 된다. 그저 한번 돌면 최선의 수를 뽑아낼 수 있다니 정말 놀라웠다... 다만 어떤 조합이 최선의 수인지는 같이 도출되지 않는 것은 아쉬웠다. 그것을 같이 도출해내려면 훨-씬 복잡해질 것 같다.

 

ex) list[3][7]을 보자.

이 물건을 넣었을 때의 최고 가치 = 이 물건의 가치 + 이 물건의 무게를 뺀 무게에서의 지금까지 알아낸 최고가치

= weight + list[2][7-3] = 6 + 8 = 14

이 물건을 안 넣었을 때의 지금까지 알아낸 최고 가치 = list[2][7] = 13

14 > 13으로 무게3 가치6인 이 물건을 넣은 수가 지금까지 알아낸 최고의 수가 되었다.

 

** list [[0 for _ in range(K+1)] for _ in range(N+1)]

을 이용하면 N*K 이차원 리스트를 0으로 초기화 할 수 있다.