clamp
Clamp
clamp
글쓰기 관리
전체 방문자
오늘
어제
  • 분류 전체보기 (509)
    • IOS (85)
    • SwiftUI+TCA+Combine (9)
    • RxSwift + MVVM (56)
    • Clean Architecture (12)
    • SWIFT (56)
    • iOS - TDD (2)
    • 디자인패턴 (4)
    • CS (56)
      • 알고리즘 (29)
      • 운영체제 (15)
      • 자료구조 (2)
      • 네트워킹 (4)
      • 기타 (6)
    • 회고 (0)
    • Firebase (18)
    • SwiftUI (10)
    • iOS - UIKit (11)
    • iOS - 오픈소스 (6)
    • 코딩테스트 (166)
      • 프로그래머스 (164)
    • 정보처리기사 (14)
    • GitHub (2)
글쓰기 / 관리자

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Swift
  • ㅅ
  • Q
  • uikit

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
clamp

Clamp

CS/알고리즘

알고리즘 - 부분 배낭 문제(Fractional Knapsack)

2022. 6. 12. 13:25

문제

n개의 물건이 각 무게와 가치를 가지고 있을 때, 한정된 용량의 배낭에 최대 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제.

물건의 전체를 넣지 못한다면 물건을 부분적으로 담는 것을 허용된다.

 

해결 방법

단위 무게당 가장 값나가는 물건을 배낭에 넣고 계속해서 그 다음으로 값나가는 물건을 넣는다.

만일 물건을 통째로 배낭에 넣을 수 없으면 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다.

 

수행 과정

배낭의 최대 용량 = 40

 

단위 무게당 가치로 정렬

물건       가치       무게      단위 그램당 가치

백금     60만원     10g             6만원

금        75만원      15g             5만원

은        10만원       25g            4천원

주석     1만원         10g            1천원

 

백금을 통째로 담는다.

배낭의 무게 = 10/40

가치 = 60만원

 

금을 통째로 담는다.

배낭의 무게 = 25/40

가치 = 135만원

 

은을 통째로 담으려 하지만 50이 되어 배나 용량이 초과하게된다.

은을 15만큼만 담는다.

4000 * 15 = 6만원

배낭의 무게 = 40/40

가치 = 141만원

 

시간 복잡도

O(n log n)
저작자표시 비영리 동일조건 (새창열림)
    'CS/알고리즘' 카테고리의 다른 글
    • 알고리즘 - 작업 스케줄링 알고리즘(JobScheduling)
    • 알고리즘 - 집합 커버 문제(Set Cover)
    • 알고리즘 - 다익스트라 알고리즘(Dijkstra Algorithm)
    • 알고리즘 - 프림 알고리즘(Prim Algorithm)
    clamp
    clamp
    주니어 iOS개발자의 발악!!!!!!!

    티스토리툴바