목록Knapsack (1)

Devlog_by_0giru

[boj] 평범한 배낭_12865

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2차원 다이나믹 프로그래밍을 활용하는 대표적인 문제다. 원래는 '안녕_1535' 문제를 풀기 위해 먼저 풀어본 문제인데, 백트래킹을 이용한 재귀함수 호출로 풀려고 시도해봤지만 시간 초과로 통과하지 못했다. pypy3로도 안되더라. 처음 내가 시도했던 방법을 그림으로 그렸다. 물건이 A B C D 네 가지가 있다고 가정한 후 각 물건을 넣느냐, 마..
[PS] 2021. 3. 29. 02:18
이전 Prev 1 Next 다음