2021.06.25
분할 가능 배낭 문제(Fractional Knapsack Problem)
분할 가능 배낭 문제(Fractional Knapsack Problem) 0-1 배낭 문제 에서 다음 조건 추가 주어진 물건(O)을 원하는 형태로 얼마든지 분할 할 수 있음. 각 물건의 일부분만을 배낭에 담을 수 있음. 실생활의 예) 상인이 기름, 곡물, 밀가루와 같은 품목을 다룰 경우 각 품목을 원하는 양만큼 덜어내서 배낭에 담을 수 있음. 일반 배낭 문제가 NP-완전 문제 인 것과 달리 분할 가능 문제 는 간단한 솔루션이 존재함. 각 물건을 단위 무게(W)당 가격(V)을 기준으로 정렬함. 그리디 방식 에 따라 단위 무게당 가격이 높은 순서 로 물건을 선택함. 분할 가능 배낭 문제의 예 배낭 용량(T)이 8인 경우에 선택할 수 있는 최선의 물건 조합 코드 #include #include #include..
