배낭알고리즘1 [백준/파이썬(Python)] 12865: 평범한 배낭 Gold 5 (냅색 알고리즘) 💌문제 https://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 💌풀이 DP를 쓰는 기본적인 문제이다. 냅색 알고리즘은 주어진 가방의 용량을 초과하지 않으면서 가치가 최대가 되도록 물건을 선택하는 최적화 문제이다. 예를 들어, 용량이 10인 가방에 물건들을 담을 때, 물건들의 가치를 최대화하려면 어떤 물건을 선택해야 하는지 결정해야 한다. Fractional Knapsack 알고리즘과 0.. 2023. 2. 21. 이전 1 다음
