[DP] 0 / 1 Knapsack

[DP] 0 / 1 Knapsack

가격은 가치를 의미

담을 수 있는 무게가 정해져 있는 가방(Knapsack)에 쪼갤 수 없는 짐을 담지 않거나 담았을 때 (0/1)

최적의 가치를 찾는 알고리즘

배낭 문제(Knapsack Problem 냅색 프라블럼)는 조합 최적화의 유명한 문제이다.

짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부르고, 동적계획법(Dynamic Programming)으로 풀 수 있다.

참고로, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem)라 부르고, 그리디 알고리즘으로 풀 수 있다.

import java.util.Scanner; public class DP3_KnapsackTest { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 물건갯수 int W = sc.nextInt(); // 가방무게 int[] weights = new int[N+1]; // 무게 int[] profits = new int[N+1]; // 가치 for (int i = 1; i <= N; i++) { // 물건 i에 따라 무게와 가치를 담기 weights[i] = sc.nextInt(); profits[i] = sc.nextInt(); } // 최적의 가치를 저장할 DP 테이블 int[][] D = new int[N+1][W+1]; // 물건 1번도 점화식에 적용시키기 위해 물건 0도 포함 // 물건 0부터,무게 0부터 DP 테이블을 채우지만, 배열 디폴트는 0이므로 물건 0인 행과 무게 0인 열은 놔두고 for문 돌린다 for (int i = 1; i <= N; i++) { // 물건 1부터 ~ 물건 N까지 for (int w = 1; w <=W ; w++) { if(weights[i] <= w) { // 해당 물건을 가방에 넣을수 있다.(믈건이 가방잔여무게보다 가볍거나 같을때) D[i][w] = Math.max(D[i-1][w], profits[i] + D[i-1][w-weights[i]]); // D[i][w] : 물건 i까지 고려한 가치를 구하는 방법은 가방잔여무게에 따라 다르게 저장한다. // 왜냐하면 다음 테이블에서 채워질 물건들의 최적의 가치는 가방잔여무게에 따라 넣을 수 있는지 없는지 달라지기 때문 //D[i-1][w] : 직전에 저장한 해당무게의 가치 // profits[i] + D[i-1][w-weights[i]] : 자신(물건 i)의 가치 + 이전 물건의 가치(D[i-1][])중에 가방잔여무게에서 자신무게를 뺀 무게(D[][w-weights[i])를 가진 가치 // 이중에 최적(최대)의 가치를 고른다.. // 즉, 물건 i를 담는것을 고려했을 때 미포함, 포함 중 어떤 가치가 나은지 판별 }else {// 해당 물건을 가방에 넣을수 없다. (물건이 가방잔여무게보다 무겁다) D[i][w] = D[i-1][w]; // 물건 i까지 고려한 가치는 직전에 저장한 해당무게의 가치(물건 i-1까지 고려한 가치중 최적의 가치)와와 같다 } } } System.out.println(D[N][W]); // 테이블의 마지막행,열의 값이 가방의 무게가 W일 때 물건 N개를 넣을 수 있는 최적의 가치 } } /* 4 10 5 10 4 40 6 30 3 50 */ // 90

from http://elevensix.tistory.com/89 by ccl(A) rewrite - 2021-09-26 18:01:19