냅색1 [ 0/1 Knapsack] 배낭 냅색 알고리즘 냅색 문제(Knapsack Problem)는 물건들의 무게 w와 가치 v가 주어지고 배낭의 용량 c가 주어질때 배낭에 넣은 물건들의 가치의 합이 최대 몇인지 구하는 문제입니다. 0/1 냅색은 물건을 쪼개어 담을 수 없는 문제입니다. 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 직관적으로 떠오르는 풀이는 특정 무게 _w에서 최대 가치의 합 dp[_w]을 구해가자! 입니다. i번째 물건의 무게와 가치를 각각 arr[i][0], arr[i][1]이.. 2020. 7. 3. 이전 1 다음
