DP

• 분할정복은 하향식 dp는 상향식 방법으로 접근

  문제제시 : 계수 값 구하기

• 이항계수 구하는 공식 (n k) = n!/k!(n-k)! for 0<= k<=n

• 계산량이 많은 n!이나 k!을 계산하지 않고 이항계수를 구하기 위해서 통상 다음 수식을 사용한다. (n k) = {if 0<k<n => (n-1 k-1) + (n-1 k) if k=0 or k=n => 1) nCk = n-1Ck-1 + n-1Ck
• 동적 계획법을 적용한 이항계수 계산

  bino(n, k)
  B[][]
  FOR i in 0 -> n
    FOR j in 0 -> minimum(i,k)
        IF j=0 OR j=i
            B[i][j] <- 1
        ELSE
            B[i][j] <- B[i-1][j-1] + B[i-1][j]
  RETURN B[n][k]
  

  ##0-1 Knapsack 알고리즘

  문제제시 : 생일선물

• 배낭문제는 n개의 물건과 각물건 i의 무게 w와 가치 v가 주어지고 배낭의 용량은 w일때, 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제이다. 단, 배낭에 담은 물건의 무게의 합이 w를 초과하지 말아야 하고, 각 물건은 1개씩만 있다.
• 배낭문제를 DB로 접근해보자
• 먼저 배낭 문제의 부분 문제를 찾아내기 위해 문제의 조어진 조건을 살펴보면
• 물건, 물건의 무게, 물건의 가치, 배낭의 용량 모두 4가지의 요소가 있다.
• 이중에서 물건과 물건의 무게는 부분 문제를 정의하는데 반드시 필요하다.
• 왜냐하면 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것과 안 담는 것을 현재 배낭에 들어 있는 물건의 가치의 합에 근거하여 결정해야 하기 때문이다.
• 또한 물건을 배낭에 담으려고 할 경우에 배낭 용량의 초과 여부를 검사해야 한다.
• 따라서 배낭문제의 부분문제를 아래와 같이 정의할 수 있다.
• W= 배낭의 용량(KG)
• (v,w) = 가치(만원), 무게(kg)물건
• k[i,w] = 물건 1~i까지만 고려하고, (임시)배낭의 용량이 w일때의 최대 가치 단, i=1,2,…,n이고, w=1,2,3..W이다.
• K[i,w]를 개쥐겆ㄱ으로 정리하면
• if i=0 or w =0 => 0
• if wi => w K[i-1, w]
• if i>- and wi <= w => max(v + K[i-1, w-w], K[i-1,w])
• 배낭 문제의 부분 문제간의 함축적 순서는 다음과 같다.
• 즉, 2개의 부분 문제 K[i-1, w-w]가 K[i-1,w]가 미리 계산되어 있어야만 K[i,w]를 계산할 수 있다.

배낭의 용량 w
n개의 물건가 각 물건 1의 무게 wi와 가치 vi, 단, i=1,2,...,n
K[n, W]

FOR i in 0 -> n : K[i,0] <- 0
FOR w in 0 -> W : K[0,w] <- 0

FOR i in 1 => n
	FOR w in 1-> W
		IF wi > w
			K[i,w] <- K[i-1,w]
		ELSE
			K[i,w] <- max(vi + K[i-1, w-wi], K[i-1,w])
RETURN K[n,W]

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++) {
			weights[i] = sc.nextInt();
			profits[i] = sc.nextInt();
		}

		int[][] D = new int[N+1][W+1];

		for(int i=1; i<=N; i++) {
			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]]);
				}else {
					//해당 물건을 가방에 넣을 수 없다.
					D[i][w] = D[i-1][w];
				}
			}
		}
		System.out.println(D[N][W]);
	}
}