C++에서 분수 배낭 문제를 해결하는 방법

C++의 분수 배낭 문제는 가방에 최대 한도를 초과하지 않고 최대 값이 포함되는 방식으로 주어진 무게와 이익의 항목을 가방에 채우는 방법을 식별하는 것을 의미합니다.

C++에서 분수 배낭 문제를 해결하는 방법

각각 주어진 무게와 이익을 가진 일련의 품목이 주어졌을 때, 품목의 총 무게가 가방의 최대 한도보다 적지만 그 가치는 가능한 한 크게 유지되어야 하는 조합의 각 품목 수를 결정합니다.

분수 배낭 문제를 구현하는 알고리즘

Knapsack 알고리즘의 기능은 다음과 같은 점을 통해 이해할 수 있습니다.

• 가중치와 이익의 두 배열을 사용합니다.
• 최대 자루 값을 W로 설정합니다.
• 두 매개변수의 비율을 취하여 밀도를 결정합니다.
• 밀도가 낮은 순서로 항목을 정렬합니다.
• <=W가 될 때까지 값을 더합니다.

분수 배낭 문제를 해결하기 위한 탐욕스러운 접근 방식

탐욕적 접근 방식은 각 단계에서 이상적인 선택을 하여 마지막에는 이상적인 솔루션을 찾는 것을 목표로 합니다. 결국 결과만 결론 짓는 것이 아니라, 문제를 단계별로 해결하여 결론을 도출합니다. 다음은 C++에서 분수 배낭 문제에 대한 솔루션을 구현하기 위한 소스 코드입니다.

이 코드에서는 가중치와 이익 값이 저장된 개체 구조가 정의됩니다. bool cmp()는 두 객체의 무게와 가치의 비율을 기반으로 두 객체를 비교하는 데 사용됩니다. 배열은 내림차순으로 정렬되며 최대값에 도달할 때까지 값이 계속 추가됩니다. 현재 값이 허용되고 한도 내에 있으면 해당 값이 추가되고, 그렇지 않으면 감소된 비율이 백에 추가됩니다. 무게와 가치의 크기는 메인 코드에 입력되고 출력에는 최대 이익이 인쇄됩니다.

스낵에 저장된 최대 수익은 580입니다.

결론

C++의 분수 배낭 문제는 가방에 최대 한도를 초과하지 않고 최대 값이 포함되는 방식으로 주어진 무게와 이익의 항목을 가방에 채우는 방법을 식별하는 것을 의미합니다. 이는 각 단계에서 이상적인 선택을 하고, 마지막에는 이상적인 솔루션을 이끌어내는 탐욕적 접근 방식을 통해 달성할 수 있습니다.