반응형
문제이름 그대로 냅색알고리즘 문제이다.
그러나 이전의 동전문제와는 달리 살짝 꼬았다.
물건(동전, 내 짐, 보석 등등) 의 종류가 무한정이라면, dp[] 앞에서부터 탐색해도 된다.
그러나 개수가 정해져 있을 때(보통은 한개임,,가끔 어려운거는 두세개임)에는 dp[] 뒤에서부터 앞으로 가야 한다.
이유는 dp[i] = dp[i-무게]+가치 로 하려할 때 자기자신을 중복해서 쓸 수도 있기 때문임.
디피에 적응될 때까지 주기적으로 연습 해야겠다...
https://www.acmicpc.net/problem/12865
코드는 짧지만 어렵다.
키포인트:
- dp[i]에서 i는 무게를 말함. i키로그람이 내 가방이 담을 수 있는 최대리밋이라면, 그때 담은 물건의 가치를 말한다.
- dp[i] = dp[i-무게]+가치 식을 쓰자. (잘 생각해보면 이해됨)
- 이 때, 같은 물건이 무한대 있지 않으므로 젤 무거운것부터 거꾸로 내려와야 한다.
import java.util.Scanner;
public class BOJ12865_평범한배낭 {
static int N, K;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
int[] dp = new int[K+1];
for(int i=0; i<N; i++) {
int weight = sc.nextInt();
int value = sc.nextInt();
for(int j=K; j>=weight; j--) {
dp[j] = Math.max(dp[j],dp[j-weight]+value);
}
}
System.out.println(dp[K]);
}
}
반응형
'개발삽질 > SSAFY하는 동안 기록' 카테고리의 다른 글
[아무내용] 백준 골드달성~~ (4) | 2022.03.19 |
---|---|
[DB] Join(inner, outer, self, natural,non-equi), Union, Index (0) | 2022.03.17 |
[BOJ]2293_동전1(dp) (0) | 2022.03.12 |
[BOJ]9370_미확인도착지(특정경로 다익스트라) (0) | 2022.03.09 |
[BOJ]6603_로또(조합) (0) | 2022.03.09 |
댓글