[JAVA] Knapsack 알고리즘
2022. 10. 11. 16:51
JAVA/알고리즘 개념 정리
Knapsack 알고리즘 이란? Knapsack은 배낭이란 뜻으로, Knapsack 알고리즘은 배낭 알고리즘 이라고도 불림 Knapsack 알고리즘은 DP의 일종으로 배낭 채우기 문제에서 유래되었음 배낭 채우기 문제란 배낭의 크기 k와 n개의 물건 각각의 무게와 가치가 주어졌을 때, 배낭에 넣은 물건들의 최대 가치의 합을 구하는 문제 ex) 무게가 7까지 담을 수 있는 배낭이 있고, 5개의 물건의 무게와 가치가 아래와 같다고 생각해 보자 물건 1 : 무게 3, 가치 8 물건 2 : 무게 1, 가치 5 물건 3 : 무게 2, 가치 7 물건 4 : 무게 2, 가치 2 물건 5 : 무게 2, 가치 6 이 때, 가방에 넣을 수 있는 최대 가치를 구해보자 만약 1번 물건(3, 8)만 있었다고 가정해보면 DP 테이..
[JAVA] 백준 12920 - 평범한 배낭 2
2022. 8. 16. 18:43
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 해결 방법 평범한 배낭 문제 푸는 방법을 안다고 가정 ( 평범한 배낭 문제 풀이 => https://chb2005.tistory.com/158 ) 평범한 배낭 문제와 유사하지만 물건들의 갯수가 1개 고정이 아닌 최대 10000개 까지 있을 수 있음 따라서 다른 해결책이 필요함 만약 물건1(무게:1, 가치:1)의 개수가 15개라고 가정해보자 처음 생각했..
[JAVA] 백준 12865 - 평범한 배낭
2022. 8. 16. 16:47
JAVA/백준(BOJ) 문제풀이
Knapsack 알고리즘 설명 및 백준 12865 문제 풀이 https://chb2005.tistory.com/158 [JAVA] Knapsack 알고리즘 ● Knapsack 알고리즘 이란? Knapsack은 배낭이란 뜻으로, Knapsack 알고리즘은 배낭 알고리즘 이라고도 불림 Knapsack 알고리즘은 DP의 일종으로 배낭 채우기 문제에서 유래되었음 배낭 채우기 문제란 배 chb2005.tistory.com