배낭 문제

1 개요

knapsack problem, rucksack problem

背囊 問題

배낭 문제

• 유명한 조합 최적화 문제
• 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제
• 어떤 수의 집합 S에 대하여, 임의의 정수를 S의 부분 집합의 합으로 나타낼 수 있는가를 묻는 문제. 또는 용량이 정해진 배낭에 가치가 다른 여러 물건을 제한된 용량 내에서 채우는 문제

 

2 같이 보기

• 배낭
• 조합 최적화
• 채우기 문제
• 연속 배낭 문제
• 부분집합 합 문제

3 참고

• 위키백과 "배낭 문제"
• 위키낱말사전 "배낭 문제"
• 다음사전 "배낭 문제"
• 다음백과 "배낭 문제"
• 네이버사전 "배낭 문제"
• 네이버백과 "배낭 문제"