설명
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);
1번
→ 위에서 아래로 방법
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)회
→ 아래에서 위로 방법
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)회
→ 아래에서 위로 방법
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))
항목이 중복되어 실패했는지 확인…
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);
}
}