배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

배낭 알고리즘이란? 배낭 문제(Knapsack)는 n개의 물건과 배낭 있을 때, 각 물건에는 가치와 무게가 존재한다. 또한 각 물건은 1개씩만 있다. 배낭에는 담을 수 있는 최대 용량이 존재한다. 이러한 조건일 때, 배낭의 최대 용량을 초과하지 않으면서 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제이다. 해당 그림은 배낭 문제의 예시이다. 지금부터 알고리즘을 설명할 때 해당 예시를 가지고 계속 설명하겠다. 0-1 KnapSack Problem 배낭 문제는 물건을 쪼갤 수 있는 Fraction Knaspack Problem과 물건을 쪼갤 수 없는 0-1 knapSack Problem으로 나뉜다. 이 글에서 설명하고자 하는 것은 0-1 KanpSack Problem이다. 대표적인 DP(Dynamic Pr..

원문링크 : 배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

 등록된 다른 글

[네트워크/Network] OSI 와 TCP/IP의 계층 구조 및 데이터 통신 과정

[네트워크/Network] OSI 와 TCP/IP의 계층 구조 및 데이터 통신 과정

[C++] 백준 16973 - 직사각형 탈출

[C++] 백준 16973 - 직사각형 탈출

[Java/C++] 프로그래머스 Level 2 - 아날로그 시계 (PCCP 기출문제 2번)

[Java/C++] 프로그래머스 Level 2 - 아날로그 시계 (PCCP 기출문제 2번)

[Unity 3D] 캔버스(Canvas)와 UI 기본 개념과 자주 쓰는 옵션 정리

[Unity 3D] 캔버스(Canvas)와 UI 기본 개념과 자주 쓰는 옵션 정리

[C++] 프로그래머스 Level 3 - 퍼즐 조각 채우기

[C++] 프로그래머스 Level 3 - 퍼즐 조각 채우기

[Java / C++] 프로그래머스 Level 3 - 외벽 점검

[Java / C++] 프로그래머스 Level 3 - 외벽 점검

[C++] 백준 18769 - 그리드 네트워크 ( 그림으로 쉽게 이해하기 )

[C++] 백준 18769 - 그리드 네트워크 ( 그림으로 쉽게 이해하기 )

[C++] 백준 2624 - 동전 바꿔주기

[C++] 백준 2624 - 동전 바꿔주기