글 읽기 - 어떤 차이가 있을까요 ? 잘 이해가 안됩니다.

chabt 4년 전 0

for(int i=1; i<=N; i++) {
for(int j=K; j>=W[i]; j--) {
dp[j] = Math.max(dp[j], dp[j-W[i]] + V[i]);
}
}

위 소스와 아래 소스에 어떤 차이가 있을까요 ?
저는 차이점을 모르겠는데,
위에 거는 맞고, 아래 거는 오류가 발생하네요. 잘 이해가 안되요. 어떤 반례가 있을까요 ?

for(int i=1; i<=N; i++) {
for(int j=W[i]; j<=K; j++) {
dp[j] = Math.max(dp[j], dp[j-W[i]] + V[i]);
}
}

import java.io.*;
import java.util.*;

public class DP_배낭1_1차원_12865 {
static int DEBUG=1;
static int N, K;
static int[] W;
static int[] V;
static long[] dp;

public static void main(String[] args) throws Exception {
exec_prepocess("DP_배낭1_12865");
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];

for(int i=1; i<=N; i++) {
st = new StringTokenizer(br.readLine());
W[i] = Integer.parseInt(st.nextToken());
V[i] = Integer.parseInt(st.nextToken());
}

dp = new long[K+1];

for(int i=1; i<=N; i++) {
for(int j=K; j>=W[i]; j--) {
    // for(int j=W[i]; j<=K; j++) {
dp[j] = Math.max(dp[j], dp[j-W[i]] + V[i]);
}
}

System.out.println(dp[K]);

}

private static void sysout(String str) {
if(DEBUG==1) System.out.println(str);
}
private static void exec_prepocess(String fname) throws Exception {
String class_name = new Object(){}.getClass().getTypeName();
class_name = class_name.substring(0, class_name.length()-2);
if(class_name.equals("Main")) DEBUG=0; 
if(DEBUG!=0) { 
System.setIn(new FileInputStream(System.getProperty("user.dir") + "\\samples\\" + fname + ".txt"));
} 
}
}

3587jjh 4년 전 1

dp테이블을 채우는 방향이 반대입니다.

dp[j-W[i]]의 값이 사전에 계산이 되어있는지 안되어있는지를 생각하면서 채워야합니다.

3587jjh 4년 전 1

이 문제의 경우는 이전 단계의 값 dp[j-W[i]]를 이용해야하는데 j를 오름차순으로 순회할 경우 현재 단계의 값이 담겨져 있게 되므로 정보를 잘못 이용하게 됩니다

chabt 4년 전 0

조언 감사드립니다.

배낭에서 고려해야 할 케이스가 많네요.

물건이 1개씩만 있을때, 무제한 있을때, N개씩 있을때 등등...

여기서는 1개씩만 있을 경우이고, 앞에서 부터 시작하면 중복이 발생하므로, 뒤에서 부터 해야 하는 거네요.

제가 쓴 방법은 무제한일 때인 경우네요.

감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 차이가 있을까요 ? 잘 이해가 안됩니다.

chabt 4년 전 0

3587jjh 4년 전 1

3587jjh 4년 전 1

chabt 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말