접근
백준의 12865번을 풀며 냅색 알고리즘에 대해서 배우게 되었다.
배낭 알고리즘이라고도 불리는데
배낭에 넣어야 하는 무게가 제한된다고 가정한다.
물건들은 각자 무게와 가치가 있고
배낭의 가치를 최대로 만들 수 있도록 물건을 넣는 것이다.
출력값은 배낭의 최대 가치이다.
이 문제를 풀 때
짐을 쪼갤 수 있느냐 없느냐에 따라 냅색 알고리즘을 푸는 방법이 달라지는데
만약 쪼갤 수 있다면 탐욕 알고리즘으로 풀 수 있고
쪼갤 수 없다면 동적 계획법으로 풀어야 한다.
사실 짐을 쪼갤 수 없다면 BFS인 너비우선탐색으로도 풀 수도 있지만 시간 초과가 발생하기 때문에 냅색 알고리즘의 동적 계획법으로 접근한다.
이 문제에서 가방을 꽉 채울 필요는 없다는 걸 기억하자.
배낭 문제를 풀기 전에 동전 교환 문제를 먼저 살펴보도록 한다.
동전 교환 문제
먼저 동전교환을 통해서 냅색 알고리즘의 성격을 파악해보록 한다.
또한 배낭문과 동전교환 문제의 차이가 무엇인지 알아보자.
(이 문제 또한 BFS로 풀 수 있지만 동전의 개수가 크기 때문에 시간 초과가 발생한다.)
접근
문제는 동전의 종류와 거슬러줘야 할 돈이 주어졌을 때
거슬러줄 동전의 개수를 최소로 하는 동전의 개수를 구하는 문제이다.
배낭 문제와 다르게 동전의 가치가 존재하지 않고 배낭문제로 따지면 무게만 주어진 것이다.
배낭 문제는 물건이 하나만 들어갈 수 있지만 동전은 개수에 제한 없이 거슬러줄 돈을 넘지 않는 선에 무한으로 들어갈 수 있다.
dp[i]=dp[i-3] +1는 무엇을 의미할까? i원을 거슬러줘야 하는 상황일 때 동전의 종류가 3원짜리 동전이라고 생각하는 것이다. dp[i-3]인 최적의 상태에 3원짜리 동전 하나를 더한 상황인 것이다.
방법
따라서 dp[i]= i원을 거슬러 줄 때의 최소 동전의 개수
최소의 동전의 수를 구하므로 dp의 기본값은 Integer.MAX_VALUE로 채우자.
풀이
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 동전 종류 1~50
int N = Integer.parseInt(br.readLine());
// 동전 종류 넣기
int[] coin = new int[N];
StringTokenizer st =new StringTokenizer(br.readLine()," ");
for(int i=0;i<N;i++){
int c = Integer.parseInt(st.nextToken());
coin[i] = c;
}
// 거슬러 줄 돈
int M = Integer.parseInt(br.readLine());
int[] dp = new int[M+1];
Arrays.fill(dp,Integer.MAX_VALUE);
exchange(M,coin, dp);
bw.write(Integer.toString(dp[M]));
bw.flush();
bw.close();
br.close();
}
static void exchange(int M, int[] coin , int[] dp){
for(int i=0;i<coin[0];i++)
dp[i]=0;
for(int j=0;j< coin.length;j++) {
int start = coin[j];
for(int i=start;i<=M;i++){
if(dp[i]>dp[i-start]+1){
dp[i] = dp[i-start]+1;
}
}
}
}
}배낭문제
접근
배낭문제와 동전 문제의 가장 큰 차이는 동전은 무한정 들어갈 수 있지만 배낭은 물건이 하나씩 존재한다는 것을 기억해야 한다.
따라서 동전 +1로 동전의 개수에 계속 누적되는 방향으로 for문을 진행했지만 배낭에는 누적이 없다.
방법
dp[i] = i무게에 들어가는 배낭의 가치가 될 것이다.
결국 "dp[i] = dp[i-K] + K의 무게를 가치 물건의 가치"
이 의미는 i-K 무게 제한이 있는 가방의 최대 가치에 K의 물건을 넣겠다는 의미이다.
풀이
import java.util.*;
import java.io.*;
public class Main{
static class Bag{
int w ;
int v ;
public Bag(int w, int v){
this.w =w;
this.v =v;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st =new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
Bag[] bag = new Bag[N];
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
int w = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
bag[i]= new Bag(w,v);
}
int[] dp = new int[K+1];
dp(bag,K,dp);
bw.write(Integer.toString(dp[K]));
bw.flush();
bw.close();
br.close();
}
static void dp(Bag[] bag, int K, int[]dp){
for(int j=0;j< bag.length;j++) {
int start = bag[j].w;
for (int i = K; i>=start; i--) {
if(dp[i]<dp[i-start]+bag[j].v) {
dp[i]=dp[i-start]+bag[j].v;
}
}
}
}
}