Knapsack

1. 0-1 Knapsack 유형

  - 배낭에 물건을 통째로 담아야 하는 문제

  - 물건을 쪼갤 수 없는 경우

  - 참고 : https://howudong.tistory.com/106

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

 

---

 

2. Fractional Knapsack

  - 물건을 부분적으로 담는 것이 허용되는 문제

  - 물건을 쪼갤 수 있는 경우

 

---

 

3. 배낭 문제 해결 (물건, 물건의 무게, 물건의 가치, 배낭의 용량)

  - 점화식

   

 

  - 코드 예제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N;	// 물건의 갯수
	static int K;	// 버틸 수 있는 무게
	static int[][] dp;	// i번째 물건까지 j (kg)을 버틸 수 있는 최대 가치
	static int[] W;	// 물건의 무게
	static int[] V; // 물건의 가치
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		W = new int[N + 1];
		V = new int[N + 1];
		dp = new int[N + 1][K + 1];
		
		for (int i = 1; i < N + 1; i++) {
			st = new StringTokenizer(br.readLine());
			W[i] = Integer.parseInt(st.nextToken());
			V[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i < N + 1; i++) {	// i번째 물건까지 고려
			for (int j = 1; j < K + 1; j++) {	// j(kg)까지 버틸 수 있는지
				if (W[i] > j) {
					dp[i][j] = dp[i - 1][j];
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], V[i] + dp[i - 1][j - W[i]]);
				}
			}
		}
		
		System.out.println(dp[N][K]);
	}
}