백준/배낭 문제
-
17845 수강 과목백준/배낭 문제 2022. 6. 5. 21:38
1. 풀이 배낭 문제 알고리즘을 사용하면 된다. 이에 대한 설명은 다음 글에 자세하게 설명해 놓았다. https://happy-fun.tistory.com/246 12865 평범한 배낭 1. 배낭 문제 알고리즘 배낭 문제 알고리즘을 이용해서 풀면 된다. 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때, 일정한 가치, 무게가 정해져 있는 짐들을 배낭에 담아야 한 happy-fun.tistory.com 2. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public..
-
12865 평범한 배낭백준/배낭 문제 2022. 6. 2. 23:10
1. 배낭 문제 알고리즘 배낭 문제 알고리즘을 이용해서 풀면 된다. 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때, 일정한 가치, 무게가 정해져 있는 짐들을 배낭에 담아야 한다. 이 때 가치의 합이 최대가 되도록 짐을 고르는 방법 두 가지로 분류 할 수 있는데, 1) 물건을 쪼갤 수 있는 배낭 문제 => 가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식 => 그리디 알고리즘 사용 2) 물건을 쪼갤 수 없는 배낭 문제 => dp를 활용해서 해결 2. 문제 풀이 이 예제는 물건을 쪼갤 수 없는 배낭 문제로 dp를 활용한다. 문제 예제를 가지고 설명하겠다. 4 7 6 13 4 8 3 6 5 12 물품의 수(N) : 4 배낭에 넣을 수 있는 최대 무게(K) : 7 item 배열의..