백준 - JAVA/동적 계획법 1
[백준] 12865번 평범한 배낭 _ JAVA ( 주석 설명 )
wch_s
2023. 3. 6. 01:52
풀이
1) dp 정의
- dp[n][k] : 각 무게에서 n번째 물건까지 담을 경우(담을 수 있는지 판별 후) 가질 수 있는 최대 가치를 저장
행 : n번째 물건
열 : 무게 k
2) 점화식
if(k - W[n] >= 0) // 담을 수 있다.
dp[n][k] = Math.max(dp[n-1][k], V[n] + dp[n-1][k - W[n]];
else
dp[n][k] = dp[n-1][k];
https://st-lab.tistory.com/141
https://fbtmdwhd33.tistory.com/60
1번
→ Top-down 방식
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int W[]; //물건의 무게를 담는 배열
static int V[]; //물건의 가치를 담는 배열
//각 인덱스가 각 물건마다 가질 수 있는 최대 가치를 담는 배열
static Integer dp[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //물품의 수
int K = Integer.parseInt(st.nextToken()); //최대로 담을 수 있는 무게
W = new int[N+1];
V = new int[N+1];
//이전 물건에 대한 가치를 메모제이션 할 때, 0번째 물건 가치를 저장하기 위해 N+1 공간
//무게 K 일 때 최대 가치를 알아내기 위한 K+1 공간을 생성한다.
dp = new Integer[N+1][K+1];
//0번째 물건 가치를 비워두기 위해(0) 1부터 시작한다.
for(int i=1;i<=N;++i){
st = new StringTokenizer(br.readLine());
W[i] = Integer.parseInt(st.nextToken()); //물건 무게
V[i] = Integer.parseInt(st.nextToken()); //물건 가치
}
System.out.println(solve(N, K));
}
//Top-down 방식
private static int solve(int N, int K) {
//이전 값 0번째 물건에 대한 가치는 0이다.
if(N==0)
return 0;
if(dp[N][K] == null){
//물건을 담을 수 있는 경우
if(K-W[N]>=0){
//이전 가치 vs 현재 무게의 가치 + 이전 값에 대한 남은 무게( K-W[N] )에 대한 가치 를 비교한다.
dp[N][K] = Math.max(solve(N-1,K), V[N] + solve(N-1, K-W[N]));
}
//물건을 추가로 담을 수 없는 경우
else{
dp[N][K] = solve(N-1, K);
}
}
return dp[N][K];
}
}
2-(1)번
→ Bottom-up 방식
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int W[]; //물건의 무게를 담는 배열
static int V[]; //물건의 가치를 담는 배열
//각 인덱스가 각 물건마다 가질 수 있는 최대 가치를 담는 배열
static int dp[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //물품의 수
int K = Integer.parseInt(st.nextToken()); //최대로 담을 수 있는 무게
W = new int[N+1];
V = new int[N+1];
//이전 물건에 대한 가치를 메모제이션 할 때, 0번째 물건 가치를 저장하기 위해 N+1 공간
//무게 K 일 때 최대 가치를 알아내기 위한 K+1 공간을 생성한다.
dp = new int[N+1][K+1];
//0번째 물건 가치를 비워두기 위해(0) 1부터 시작한다.
for(int i=1;i<=N;++i){
st = new StringTokenizer(br.readLine());
W[i] = Integer.parseInt(st.nextToken()); //물건 무게
V[i] = Integer.parseInt(st.nextToken()); //물건 가치
}
solve2(N, K);
System.out.println(dp[N][K]);
}
private static void solve2(int N, int K){
for(int i=1;i<=N;++i){ //N번째 물건
for(int j=1;j<=K;++j){ //각 무게에서 가질 수 있는 최대 가치
//물건을 넣을 수 있으면
if(W[i]<=j){
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-W[i]] + V[i]);
}
//물건을 추가할 수 없으면
else
dp[i][j] = dp[i-1][j];
}
}
}
}
2-(2)번
→ Bottom-up 방식
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int W[]; //물건의 무게를 담는 배열
static int V[]; //물건의 가치를 담는 배열
//각 인덱스가 각 물건마다 가질 수 있는 최대 가치를 담는 배열
static int dp[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //물품의 수
int K = Integer.parseInt(st.nextToken()); //최대로 담을 수 있는 무게
W = new int[N+1];
V = new int[N+1];
//이전 물건에 대한 가치를 메모제이션 할 때, 0번째 물건 가치를 저장하기 위해 N+1 공간
//무게 K 일 때 최대 가치를 알아내기 위한 K+1 공간을 생성한다.
dp = new int[K+1];
//0번째 물건 가치를 비워두기 위해(0) 1부터 시작한다.
for(int i=1;i<=N;++i){
st = new StringTokenizer(br.readLine());
W[i] = Integer.parseInt(st.nextToken()); //물건 무게
V[i] = Integer.parseInt(st.nextToken()); //물건 가치
}
solve3(N, K);
System.out.println(dp[K]);
}
private static void solve3(int N, int K){
for(int i=1;i<=N;++i){ //N번째 물건
//무계의 한계치까지 반복 수행한다.
//각 무게에서 가질 수 있는 최대 가치
for(int j=K;j-W[i]>=0;--j){
//N번째 무게의 가치 + 남은 무게의 가치가 크다면 그 값을 갱신해준다.
dp[j] = Math.max(dp[j], dp[j-W[i]] + V[i]);
}
}
}
}
* 잘못된 접근
dp[] : '각 무게가 가질 수 있는 최대 가치' 으로 정의하고
dp[5] 이라면 Math.max(dp[1] + dp[4], dp[2] + dp[3]) 방식으로 접근했으나
1개의 물건이 중복적으로 담겨지는 것을 확인하고 실패...
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int ary[][]; //물건의 무게와 가치를 담는 배열
static Integer dp[]; //각 인덱스가 담을 수 있는 최대 무게라 가정하고, 가질 수 있는 최대의 가치를 담는 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //물품의 수
int K = Integer.parseInt(st.nextToken()); //최대로 담을 수 있는 무게
ary = new int[N][2];
//K의 무게까지 표현할 수 있어야한다.
//입력되는 물건의 무게가 없는 것들은 무게를 0으로 산정해야한다. (int 배열을 사용하면 '0'의 의미가 생기므로 dp[] 메모제이션 체크 불가)
//Integer 배열로 선언해 무한 반복을 피한다.
dp = new Integer[K+1];
for(int i=0;i<N;++i){
st = new StringTokenizer(br.readLine());
ary[i][0] = Integer.parseInt(st.nextToken()); //물건 무게
ary[i][1] = Integer.parseInt(st.nextToken()); //물건 가치
if(dp[ary[i][0]] == null)
dp[ary[i][0]] = ary[i][1];
else{ //동일한 무게이나 가치가 더 높은 물건이 나올 시 가치를 갱신해준다.
dp[ary[i][0]] = Math.max(dp[ary[i][0]], ary[i][1]);
}
}
System.out.println(solve(K));
for(int i=0;i<=K;++i){
System.out.println(dp[i]);
}
}
private static int solve(int K) {
if(dp[K]==null) { //dp[K]가 메모제이션이 안 되어 있으면 계산을 시작한다.
dp[K] = 0; //기본적으로 'K'의 무게를 가진 물건(가치)가 없으므로 0으로 설정한다.
//K가 짝수일 때 : 중앙값이 두 번 사용된다,
int range_K = (K%2==0) ? K/2 : K/2+1;
for (int i = 1; i < range_K; ++i) { //(K/2) 이후는 중복 계산이므로 생략한다.
dp[K] = Math.max(dp[K], solve(K-i) + solve(i));
}
}
return dp[K];
}
}