Algorithm. Greedy Algorithm

[Visual Studio과 C#으로 구현/부분배낭문제]

Algorithm Greedy Algorithm Coding // Week09

20211028_20615034

[ Greedy Algorithm Coding_Theory ]

부분 배낭 문제

- 배낭 (Knapsack) 문제
n개의 물건이 있고,
각 물건은 무게와 가치를 가지고 있으며,
배낭이 한정된 무게의 물건들을 담을 수 있을 때,
최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제
​

- 부분 배낭 (Fractional Knapsack) 문제
물건을 부분적으로 담는 것을 허용
그리디 알고리즘​으로 해결

​
- 0-1 배낭 문제 (0/1 배낭 문제)
부분 배낭 문제의 원형으로 물건을 통째로 배낭에 넣어야 한다.
동적 계획 알고리즘, 백트래킹 기법, 분기 한정 기법으로 해결
​

- 부분 배낭 문제
: 부분 배낭 문제에서는 물건을 부분적으로 배낭에 담을 수 있으므로, 최적해를 위해서 ‘욕심을 내어’ 단위 무게 당 가장 값나가는 물건을 배낭에 넣고, 계속해서 그 다음으로 값나가는 물건을 넣는다.
그런데 만일 그 다음으로 값나가는 물건을 ‘통째로’ 배낭에 넣을 수 없게 되면, 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다.

[ Greedy Algorithm Coding_Code ]

[ Greedy Algorithm Coding_Code loot ]

Q. 다음 그림과 같은 4개의 금속 분말이 있고, 배낭의 최대 용량은 40그램이다.
​

A.

단위그램당 가치

-> 주석: 천원

-> 백금: 6만원

-> 은: 4천원

-> 금: 5만원

Line 1~2의 결과
-> S=[백금, 금, 은, 주석]

Line 3

-> L=∅, w=0, v=0로 각각 초기화한다.

Line 4

-> S=[백금, 금, 은, 주석]로부터 백금을 가져온다.

Line 5

-> while-루프의 조건 ((w+백금의 무게) ≤ C) = ((0+10)<40)이 ‘참’이다.

Line 6

-> 백금을 배낭 L에 추가시킨다. 즉, L=[백금]이 된다.

Line 7

-> w = w(백금의 무게) = 0+10g = 10g

Line 8

-> v = v(백금의 가치) = 0+60만원 = 60만원

Line 9

-> S에서 백금을 제거한다. S=[금, 은, 주석]

Line 10

-> S에서 금을 가져온다.