https://jeonyeohun.tistory.com/86 [알고리즘 정리] 배낭 문제(Knapsack Problem) Knapsack Problem Knapsack Problem, 배낭문제는 다이나믹 프로그래밍에서 매우 유명한 문제이다. 어떤 배낭이 있고 그 배낭안에 넣을 수 있는 최대 무게가 K라고 하자. 배낭에 넣을 수 있는 N개의 물건이 jeonyeohun.tistory.com 예제로는 [백준 12865번] 평범한 배낭을 참고한다. 이 문제는 NP-hard문제이다. optimazation problem 모든 경로를 탐색하여 최적해를 찾는 문제!! DP를 이용해야겠지?? 경로: 해당 무게로 만들 수 있는 조합 값: V가치 1. top - down 방식 2. bottom - up 방식 tabulat..

1. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 중복을 허락하여 해당 동전을 만들 수 있는 경우이므로 자연수 분할, 즉 중복 조합문제이다. 2. 풀이 아이디어(시행착오) 동전 n개로 k원을 만들 수 있는경우의 수를 구하는 문제이다. 언뜻 보기엔 일반적인 DFS로 재귀를 이용한 top - down방식으로 풀 생각이 들 수 있다. 예들 들어 1, 2원짜리 동전을 가지고 4원을 만드는 경우 3원(4 - 1원)에 1원을 더한 것과 2원(4 -..