https://st-lab.tistory.com/141
[백준] 12865번 : 평범한 배낭 - JAVA [자바]
www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤..
st-lab.tistory.com
https://hongcoding.tistory.com/50
[백준] 12865 평범한 배낭(Python 파이썬)
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무..
hongcoding.tistory.com
https://velog.io/@uoayop/%EB%83%85%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
냅색 알고리즘
골라골라
velog.io
https://www.acmicpc.net/board/view/60752
글 읽기 - Knapsack 알고리즘(배낭알고리즘dp) 질문ㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static int N,K;
static Integer[][] dp;
static int[] W;
static int[] V;
public static void main(String arg[]) throws IOException {
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];
V = new int[N];
dp = new Integer[N][K+1];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
W[i] = Integer.parseInt(st.nextToken());
V[i] = Integer.parseInt(st.nextToken());
}
System.out.println(knapsack(N-1, K));
}
static int knapsack(int i, int k) {
if(i < 0) {
return 0;
}
if(dp[i][k] == null) {
if(W[i] > k) { //현재 무게가 w[i]를 받지 못하면
dp[i][k] = knapsack(i-1, k); //이전 i값을 탐색한다 (표에서 바로 위의 값)
}
else { //받을 수 있다면
dp[i][k] = Math.max(knapsack(i-1,k), knapsack(i-1, k-W[i]) + V[i]);
//이전 i값(표에서 위의 값)과 이전 i의 값(현재의 i가 포함되면 안됨) 중 현재 k의 무게에서 i 의 무게 w[i]를 뺀 무게의 가치+현재 무게의 가치
}
}
return dp[i][k];
}
}
'백준' 카테고리의 다른 글
[백준] 25178 두라무리 휴지 [자바] (0) | 2022.05.18 |
---|---|
[백준] 25194 결전의 금요일 [자바] (0) | 2022.05.16 |
[백준] 11725 트리의 부모 찾기 [자바] (0) | 2022.05.04 |
[백준] 2448 별 찍기 - 11 [자바] (0) | 2022.04.25 |
[백준] 1629 곱셈 [자바] (0) | 2022.04.22 |