0-1 배낭 채우기 동적 계획법 자바 구현

정해진 가방의 무게에 물건을 채우는데 각 물건은 가치와 무게가 정해져있다. 그 때 최대한의 가치로 가방을 채우는 알고리즘이 배낭 채우기이다. 동적 계획법으로 아래와 같이 구현했다. 일단 아래의 변수들을 전역으로 선언했다. static int num; // 물건의 수 static int maxWeight; // 가방에 들어갈 수 있는 무게 static int[] weight; // 무게들의 배열 static int[] value; // 가치들의 배열 static int[][] dp; // 답을 구할 배열 static int maxValue = 0; // 구한 답에서 최대의 가치 아래는 알고리즘 부분이다. public static void napsack() { int w = weight[0]; for(int i = w; i < maxWeight + 1; i++) dp[0][i] = value[0]; for (int i = 1; i < num; i++) { w = weight[i]; fo...

원문링크 : 0-1 배낭 채우기 동적 계획법 자바 구현