분기 결합 방법을 사용하여 C/C++에서 0/1 배낭 문제 구현

탐욕적인 방법이 분수 배낭 문제에 대한 최선의 해결책을 제공한다는 사실을 깨닫는 것이 아이디어입니다.

특정 노드가 더 나은 솔루션을 제공할 수 있는지 확인하기 위해 탐욕스러운 접근 방식을 구현하여 (노드별로) 최상의 솔루션을 계산합니다. 그리디 방법 자체가 지금까지의 최상의 솔루션보다 더 많은 솔루션을 계산한다면 노드를 통해 더 나은 솔루션을 얻을 수 없습니다.

완전한 알고리즘은 다음과 같습니다. -

• 탐욕법을 사용하여 상한값을 계산할 수 있도록 모든 항목을 단위 중량당 값의 내림차순으로 정렬합니다.

• 최대 이익을 초기화합니다. 예를 들어 maxProfit = 0

• 빈 대기열을 만듭니다. Q.

• Decision 가상 노드는 트리를 생성하고 이를 Q에 삽입하거나 대기열에 추가합니다. 가상노드의 수익과 가중치는 0이다.

• Q가 비어 있지 않거나 비어 있을 때 다음 작업을 수행합니다.

  • Q에서 프로젝트를 만들었습니다. 추출 항목을 u로 둡니다.

  • 다음 레벨 노드의 수익을 계산합니다. 이익이 maxProfit보다 높으면 maxProfit을 수정하세요.

  • 다음 레벨 노드의 경계를 계산합니다. 경계가 maxProfit보다 높으면 다음 레벨 노드를 Q에 추가합니다.

  • 다음 레벨 노드가 솔루션의 일부로 고려되거나 고려되지 않고 다음 레벨의 큐에 노드를 추가하지만 가중치와 이익이 다음 레벨 노드를 처리하거나 고려하지 않는 경우를 고려하십시오.

아래 그림 -

Input

// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10

Output

The maximum possible profit = 235

위 내용은 분기 결합 방법을 사용하여 C/C++에서 0/1 배낭 문제 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!