knapsackproblem1 0-1 knapsack problem 가방에 최대 무게가 있고 그 무게 안에 물건을 넣는데 물건의 가치가 최대로 넣는 경우를 구하는 문제. Brute force로 문제를 풀면 모든 가능한 부분집합의 경우를 비교해보면 되므로 2의 n번을 비교해보게 된다. 예를 들어 보석1, 2, 3, 4 가 있고 각각의 무게와 가치가 있을 때 0부터 최대 가방무게 n까지 열의 속성으로 두고 0부터 최대 보석 가지수를 4개까지 행이 속성으로 두어서 보석 가지 수⑊가방 무게 0 1 2 .. n 0 0 0 0 0 1 0 2 0 3 0 4 0 이런 식으로 테이블이 만들어진다 생각하고 이해해보면 쉽다. 처음에 이 문제를 이해하려고 했을 때 많이 애를 먹었던 부분이 왜 보석을 여러개를 안넣고 1개만 넣는거지??였다. 예를들어 보석1의 무게가 1이면 가방 무게가 2이므로.. 2021. 6. 9. 이전 1 다음