본문 바로가기

백준

[백준] 12865 평범한 배낭 [자바]

 

 


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];
 	}
}