반응형
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
Knapsack Problem으로 유명한 문제, DP의 대표적인 유형이라고 한다.
상세한 문제 풀이는 이곳에서 볼 수 있다.
https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C
[DP] 0/1 Knapsack(배낭) 문제
배낭문제(Knapsack Problem)란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다 배낭에..
huiyu.tistory.com
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 11053. 가장 긴 증가하는 부분 수열 (LIS) (0) | 2019.12.22 |
|---|---|
| [Python] 프로그래머스. 버스 여행 (Level 4) (0) | 2019.12.21 |
| [Python] 백준 7569. 토마토 (0) | 2019.12.19 |
| [Python] 프로그래머스. 2018 카카오 recruit - 뉴스 클러스터링 (0) | 2019.12.18 |
| [Python] 프로그래머스. FloodFill (Level 3) (0) | 2019.12.17 |