knapsack 예제

위키백과에서, 우리는 배낭 문제의 몇 가지 변형이 있다는 것을 볼 수 있습니다 : 0-1 배낭, 경계 배낭, 그리고 무한 배낭. 오늘은 가장 일반적인 (그리고 가장 간단한) 변형인 0-1 배낭 문제에 초점을 맞출 것입니다. 배낭 문제는 조합에서 정말 흥미로운 문제입니다 – 위키 백과를 인용, 다차원 배낭은 배낭보다 계산적으로 어렵다; D = 2 {디스플레이 스타일 D=2} 경우에도 P = {디스플레이 스타일 =} NP가 아니면 EPTAS가 없는 문제입니다. [22] 그러나[23]의 알고리즘은 희소 인스턴스를 효율적으로 해결하는 것으로 나타났다. 다차원 배낭의 인스턴스는 설정J = { 1 , 2 , … … ❏ jj에 J { z } 이러한 인스턴스는 예를 들어 릴레이 노드가 있는 무선 네트워크에서 패킷을 예약할 때 발생합니다. [23] [23]의 알고리즘은 객관식 변형인 객관식 다차원 배낭의 희소인스턴스도 해결합니다. 이 튜토리얼에서 우리는 0 1 배낭 문제에 대해 배울 것입니다.

이 동적 프로그래밍 문제에서 우리는 관련 가중치와 값 (이익 또는 이익)을 가진 n 항목이 각각 있습니다. 목표는 우리가 배낭의 무게 제한을 교차하지 않고 최대 이익을 가지고 있도록 항목으로 배낭을 채우는 것입니다. 이것은 0 1 배낭 문제이기 때문에 전체 항목을 가져 가거나 완전히 거부 할 수 있습니다. 우리는 항목을 중단하고 배낭을 채울 수 없습니다. 열 번호 j는 배낭의 중량 용량을 나타냅니다. 따라서 예를 들어 열 5의 값은 배낭이 5개의 가중치 단위를 보유할 수 있다고 가정합니다. 자신의 가치와 무게를 가진 W 및 N 항목의 최대 용량의 배낭을 감안할 때, 최종 내용이 최대 값을 가지고 있도록 배낭 내부에 항목을 던져. 저런!! 이 행렬의 각 값은 더 작은 배낭 문제를 나타냅니다. 이 자습서에서는 두 가지 예제가 있습니다. 다음은 위의 프로그램을 실행하는 자바 코드입니다 두 가지 예 : 구체적인 예제를 표시하기 전에 먼저 논리를 설명합니다. Knapsack 문제는 두 가지 유형으로 나눌 수 있습니다: Knapsack 문제는 원자재를 절단하는 가장 낭비되는 방법을 찾는 것과 같은 다양한 분야에서 실제 의사 결정 프로세스에 나타납니다,[4] 투자 및 포트폴리오의 선택,[5] 자산 담보 증권화를 위한 자산 선택[6] 및 Merkle-Hellman[7] 및 기타 배낭 암호 시스템에 대한 키 생성. 3) 다음 및 가장 중요한 이벤트는 열 9 및 행 2에서 발생합니다.

즉, 무게는 9이고 두 가지 항목이 있습니다. 예제 데이터를 살펴보면 처음 두 항목을 수용할 수 있습니다. 여기서는 이러한 변화가 배낭을 채우는 개인의 목표를 변경합니다. 금전적 이익을 극대화하는 것과 같은 하나의 목표 대신, 목표는 여러 차원을 가질 수 있습니다. 예를 들어, 경제적 목표뿐만 아니라 환경적 또는 사회적 문제가 있을 수 있습니다. 자주 해결되는 문제로는 포트폴리오 및 운송 물류 최적화가 포함됩니다. [20] [21] 나는 동시에 배낭 문제가 까다롭고 흥미로운 것을 발견했다. 이 페이지를 방문하는 경우, 당신은 이미 문제 문을 알고 있지만 완료를 위해 : 예를 들어, 당신은 유람선을 실행 가정합니다.

당신은 고용 할 얼마나 많은 유명한 코미디언을 결정해야합니다. 이 보트는 승객의 더 이상 1 톤을 처리 할 수 있으며, 연예인은 1000 파운드 미만의 무게를해야합니다. 각 코미디언은 무게를 가지고, 자신의 인기에 따라 사업을 제공하고 특정 급여를 요청합니다. 이 예제에서는 여러 목표가 있습니다. 물론 연예인의 급여를 최소화하면서 인기를 극대화하고 싶을 것입니다.