0-1 배낭 문제(0-1 Knapsack Problem)의 핵심 특징은?

Q: 0-1 배낭 문제(0-1 Knapsack Problem)의 핵심 특징은?

각 물건을 넣거나 넣지 않는 두 가지 선택만 가능하며, 무게 제한 내에서 가치를 최대화하는 조합을 찾는다 0-1 배낭 문제는 각 물건을 통째로 넣거나(1) 안 넣거나(0)만 가능합니다. 그리디로는 최적해를 보장할 수 없어 동적 프로그래밍으로 풀며, 시간 복잡도는 O(nW)(n: 물건 수, W: 배낭 용량)입니다. 자원 배분, 예산 최적화 등에 활용됩니다.

보통 freeCodeCamp

보기 및 정답

A 각 물건을 넣거나 넣지 않는 두 가지 선택만 가능하며, 무게 제한 내에서 가치를 최대화하는 조합을 찾는다

B 각 물건을 쪼개어 일부만 넣을 수 있으며, 무게 대비 가치가 높은 순서대로 담아 가치를 극대화하는 분할 배낭 문제이다

C 배낭의 무게 제한 없이 주어진 모든 물건을 전부 넣으며, 가치의 총합을 단순히 계산하는 문제이다

D 그리디 방식으로 가장 가벼운 물건부터 순서대로 넣어 배낭의 공간을 최대한 활용하는 문제이다

해설

0-1 배낭 문제는 각 물건을 통째로 넣거나(1) 안 넣거나(0)만 가능합니다. 그리디로는 최적해를 보장할 수 없어 동적 프로그래밍으로 풀며, 시간 복잡도는 O(nW)(n: 물건 수, W: 배낭 용량)입니다. 자원 배분, 예산 최적화 등에 활용됩니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

0-1 배낭 문제(0-1 Knapsack Problem)의 핵심 특징은?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

시장과 사람의 답을 봤다면,다음 결과물의 구조를 고릅니다.

시장과 사람의 답을 봤다면,
다음 결과물의 구조를 고릅니다.