π 0-1 λ°°λ λ¬Έμ
π« 0-1 λ°°λ λ¬Έμ
λ°°λμ μ΄λ€ 물건μ λ΄μμΌ μ΅λ μ΄μ΅μ λΌ μ μλμ§ μμλ΄λ λ¬Έμ μ΄λ€.
κ° λ¬Όκ±΄μ ν΅μ§Έλ‘ λ£κ±°λ μμ μ λ£κ±°λ νμΌν΄μΌ νλ€λ μ‘°κ±΄μ΄ μμ λ, λ°°λμ μ©λμ λμ§ μμΌλ©΄μ λ°°λμ λ΄μ μ μλ 물건λ€μ μ΅λ μ΄μ΅μ΄ μΌλ§μΈμ§(μ ννκ²λ μ΅λ μ΄μ΅μ μ»μ΄λ΄κΈ° μν΄ μ΄λ€ 물건μ λ΄μμΌ νλμ§) μμλ΄λ λ¬Έμ
- μμ¬μμ΄ λ°©λ²μΌλ‘ ν΄κ²°ν μ μμ
- λΆν μ 볡과 λμ κ³νλ²μ μ΄μ©νμ¬ ν΄κ²°
μ΅μ ν λ¬Έμ
@ TODO : Tex κ΄νΈ
- nκ°μ 물건 $ S = { Object_1, β¦, Object_n } $
- κ° λ¬Όκ±΄μ λ¬΄κ² $ W = { w_1, β¦, w_n } where\ w_i > 0 $
- κ° λ¬Όκ±΄μ μ΄μ΅ $ P = { p_1, β¦, p_n } where\ p_i > 0 $
- κ° λ¬Όκ±΄μ΄ λ°°λμ λ£μ΄μ§λ λΆλΆ $ X = { x_1, β¦ x_i } where\ x_i = 0 or 1 $
- λ°°λμ μ©λ $ M > 0 $
- μ΅μ ν΄ $ K(n, M) $ μ $ \sum_{i = 1}^n p_i x_i $ μ μ΅λκ°. λ¨. $ \sum_{i = 1}^n w_i x_i \le M $
π« Solve By Dynamic-Programming
물건μ 무κ²μ μμ μ€μλ₯Ό νμ©νλ€λ©΄ λμ κ³νλ²μ μ΄μ©νλλ° μ΄λ €μμ΄ μμ (why??)
- 무μμ κΈ°λ²
- κ°λ₯ν λͺ¨λ 물건μ μ‘°ν©(2nκ°)μ ꡬνκ³
- λ°°λμ μ©λμ μ΄κ³Όνλ μ‘°ν©μ λͺ¨λ μ μΈν λ€μ
- λ¨μ μ‘°ν©λ€ κ°μ΄λ° μ΄μ΅μ΄ μ΅λμΈ κ²μ μ°Ύμ
- μ΅μ λΆλΆκ΅¬μ‘°
- λ°°λ μ©λ $ = M $ μ΄κ³ μ΅μ ν΄ $ = K(n, M) $ μΌ λ, μ΅μ ν΄ μνμ λ°°λμ κ΄μ°°
- $ object_n $ μ΄ λ°°λμ μλ€ : μ μ΄μ $ object_n $ μ΄ μλ μνμμ λ¬Έμ λ₯Ό νμ΄λ κ°μ κ²°κ³Ό.
- μ¦, $ K(n, M) = K(n - 1, M) $
- $ object_n $ μ΄ λ°°λμ μλ€ : λ°°λμ $ object_n $ μ 미리 λ£μ΄λ μνμ μ΅μ ν΄μ λμΌ.
- μ¦, $ K(n, M) = K(n - 1, M - w_n) + p_n $
- β΄ μ΅μ λΆλΆκ΅¬μ‘°λ₯Ό κ°μ§
- $ object_n $ μ΄ λ°°λμ μλ€ : μ μ΄μ $ object_n $ μ΄ μλ μνμμ λ¬Έμ λ₯Ό νμ΄λ κ°μ κ²°κ³Ό.
- λ 쑰건μ λ°λ₯Έ λΆλ¬Έμ μ μ΅μ ν΄λ₯Ό μ΄μ©νλ©΄ μλ λ¬Έμ λ₯Ό ν΄κ²° κ°λ₯
- i.e. $ M = 30, W = {5, 10, 25}, P = {150, 150, 200} $μ΄ μ£Όμ΄μ‘μ λ μ΅μ ν΄ $ K(3, 30) $ ?
- β 3λ²μ§Έ λ¬Όκ±΄μ΄ μ΅μ ν΄μ λ°°λμ ν¬ν¨λμ§ μλλ€λ κ°μ νμ μ΅μ ν΄μΈ $ K(2, 30) $ κ³Ό 3λ²μ§Έ λ¬Όκ±΄μ΄ μ΅μ ν΄μ λ°°λμ ν¬ν¨λλ€λ κ°μ νμ μ΅μ ν΄μΈ $ K(2, 5) + 200 $ κ°μ΄λ° λ ν° κ°
- i.e. $ M = 30, W = {5, 10, 25}, P = {150, 150, 200} $μ΄ μ£Όμ΄μ‘μ λ μ΅μ ν΄ $ K(3, 30) $ ?
- λΆλ¬Έμ λ₯Ό μ μνλ νμ
- μ°μλ νλ ¬ κ³±μ
, μ΅μ μ΄μ§ νμ νΈλ¦¬μ λΆλ¬Έμ λ μμκ³Ό λμ΄ λ§€μ° μ€μ
- i.e. λΆλ¬Έμ $ M_i β¦ M_j $ μμ μ‘°κΈμ© $ i $ μ $ j $μ μ°¨λ₯Ό λλ € μ΅μ’ μ μΌλ‘ $ M_1 β¦ M_n $μ μ΅μ ν΄λ₯Ό ꡬν¨
- λμ κ±°μ€λ¦λ λ¬Έμ , 0-1 λ°°λ λ¬Έμ λ λΆλ¬Έμ μ νμͺ½ κ²½κ³λ μΈμ λ μΌμ
- i.e. λΆλ¬Έμ $ { object_1 , β¦ , object_i } $μμ μ‘°κΈμ© $ i $ λ₯Ό λλ € μ΅μ’ μ μΌλ‘ $ { object_1, β¦ , object_n } $ μ λν μ΅μ ν΄λ₯Ό ꡬν¨
- λΆλ¬Έμ κ° νμ $ K(1, j, m) $ μΌλ‘ μ μλκΈ° λλ¬Έμ μμ λΆλΆμ μ μΈν $ K(n, M) $ μΌλ‘λ μΆ©λΆ
- μ°μλ νλ ¬ κ³±μ
, μ΅μ μ΄μ§ νμ νΈλ¦¬μ λΆλ¬Έμ λ μμκ³Ό λμ΄ λ§€μ° μ€μ
- λ°°λ μ©λ $ = M $ μ΄κ³ μ΅μ ν΄ $ = K(n, M) $ μΌ λ, μ΅μ ν΄ μνμ λ°°λμ κ΄μ°°
@ KP_A
- λ¬Έμ μ μνμ μ μ
- μ΅μ’ λͺ©ν: μ΅λ μ΄μ΅μ κ°μ Έλ€ μ£Όλ 물건μ μ‘°ν©
- μ΅μ°μ λͺ©ν: μ΅λ μ΄μ΅
- $ n $ κ°μ λ¬Όκ±΄μ΄ μ£Όμ΄μ§κ³ λ°°λ μ©λμ΄ $ M $ μΈ 0-1 λ°°λ λ¬Έμ μ μ΅μ ν΄ $ K(n, M) $
- $ object_n $μ΄ λ°°λμ ν¬ν¨λμ§ μλλ€λ κ°μ νμ μ΅μ ν΄μ ν¬ν¨λλ€λ κ°μ νμ μ΅μ ν΄ μ€ λ ν° κ°
- $ K(n, M) = Max { K(n - 1, M), K(n - 1, M - w_n) + p_n } $
- $ n $ κ°μ λ¬Όκ±΄μ΄ μ£Όμ΄μ§κ³ λ°°λ μ©λμ΄ $ M $ μΈ 0-1 λ°°λ λ¬Έμ μ μ΅μ ν΄ $ K(n, M) $
- μΌλ°ν
- $ i $ κ°μ λ¬Όκ±΄μ΄ μ£Όμ΄μ§κ³ λ°°λ μ©λμ΄ $ w $ μΈ 0-1 λ°°λ λ¬Έμ μ μ΅μ ν΄ $ K(i, w) $
- $ object_i $ κ° λ°°λμ ν¬ν¨λμ§ μλλ€λ κ°μ νμ μ΅μ ν΄μ ν¬ν¨λλ€λ κ°μ νμ μ΅μ ν΄ μ€ λ ν° κ°
- λ¬Όκ±΄μ΄ μκ±°λ λ°°λ μ©λμ΄ 0 β μ΅μ ν΄κ° 0
- $ object_i $ μ 무κ²κ° λ°°λμ μ©λμ λμ΄μλ μν© β $ object_i $κ° μ΅μ ν΄μ λ°°λμ ν¬ν¨λμ§ μμ κ²½μ°λ§ κ³ λ €
- $ i $ κ°μ λ¬Όκ±΄μ΄ μ£Όμ΄μ§κ³ λ°°λ μ©λμ΄ $ w $ μΈ 0-1 λ°°λ λ¬Έμ μ μ΅μ ν΄ $ K(i, w) $
1
2
3
4
5
6
7
8
9
10
11
// w[]μ p[]λ κ° λ¬Όκ±΄μ 무κ²μ μ΄μ΅μ λ΄μ λ°°μ΄
int DC_01_ks(int i, int w)
{
if (i == 0 || w == 0)
return 0;
if (w < W[i])
return DC_01_ks(i - 1, w);
return Math.Max(DC_01_ks(i - 1, w), DC_01_ks(i - 1, w - W[i]) + P[i]);
}
- μ€μ²©λ λΆλ¬Έμ μ λΆν μ 볡
- 볡μ‘λ β νΈλ¦¬μ μλ λ
Έλ μ = μ΅λ $ \sum_{l = 1}^n 2^l $ = μ΅λ $ 2^{2 + 1} - 1 = O(2^n) $
- 무μμ κΈ°λ² $ Ζ(2^n) $ κ³Ό λΉμ·, but μ€μ λ‘ νΈμΆλλ λ Έλ μλ λ³΄ν΅ μ΄λ³΄λ€ μ μ
- μκ³ λ¦¬λ¬μ κ°μ νλ©΄ λ¨λ§ λ Έλ νΈμΆμ μμ¨ μ μμ
- μ€μ²©λ λΆλ¬Έμ νΉμ±
- 물건 κ°μκ° λ§μμλ‘ λ°°λ μ©λμ΄ μμμλ‘ λΆλ¬Έμ κ° μ€λ³΅λ κ°λ₯μ±μ΄ 컀μ§
- 볡μ‘λ β νΈλ¦¬μ μλ λ
Έλ μ = μ΅λ $ \sum_{l = 1}^n 2^l $ = μ΅λ $ 2^{2 + 1} - 1 = O(2^n) $
@ KP_B
@ κ°λ°© 곡κ°μ΄ μ μ΄μ κ³μ°νμ§ μλ, λΆλ¬Έμ κ° νλ λ°μ μλ μΌμ΄μ€κ° μκΈΈ μ μμ
λμ κ³νλ²μΌλ‘ νκΈ° : ν¨μ λμ λ°°μ΄λ‘
𫧠DP 1 - μκ³ λ¦¬λ¬
- μ΅μ°μ λͺ©ν: $ n $ κ°μ 물건과 λ°°λ μ©λμ΄ $ M $ μΈ 0-1 λ°°λ λ¬Έμ μ μ΅λ μ΄μ΅ $ K(n, M) $
- 2μ°¨μ λ°°μ΄μ μμ $ K[i][w] $ μ $ K(i, w) $μ κ°μ μ μ₯νκ³ νμν λλ§λ€ μ¬μ¬μ©
- 1μ°¨μ λ°°μ΄μ μμ $ P[i] $ κ³Ό $ W[i] $ μ κ°κ° $ object_i $ μ μ΄μ΅κ³Ό 무κ²κ° μ μ₯
@ KP_C
@ KP_D
@ λ°°μ΄ Bκ° λ°λμ μμ΄μΌ νλ? μμ΄λλ¨ κ·Όλ° μΌλ¨ νλλ°λ‘ κ³μ°νλ €κ³
𫧠DP 1 - ꡬν
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// W[ ]μ P[ ]λ κ° λ¬Όκ±΄μ 무κ²μ μ΄μ΅μ λ΄μ λ°°μ΄
int _01_ks_DP(int n, int M)
{
int[][] K = new int[MAX][MAX];
for (int w = 0; w <= M; w++)
K[0][w] = 0;
for (int i = 0; i <= n; i++)
K[i][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int w = 1; w <= M; w++)
{
if (w < W[i])
K[i][w] = K[i - 1][w];
else
K[i][w] = Math.Max(K[i - 1][w], K[i - 1][w - W[i]] + P[i]);
}
}
return K[n][M];
}
𫧠DP 1 - λΆμ
- 볡μ‘λ: $ Ζ(nM) $ vs. λΆν μ 볡 μκ³ λ¦¬μ¦μ 볡μ‘λ $ O(2^n) $
- μ΄λ μͺ½μ μ±λ₯μ΄ λ μ’μκ°? : βμ μ μλ€β
- Mμ κ°μ΄ λ§€μ° ν¬λ©΄ λΆν μ 볡 μκ³ λ¦¬μ¦μ μ±λ₯μ΄ λ λμ μλ μμ
- μ) $ M = O(n!) $ μ΄λ©΄ DP 1μ $ O(n!) $
- μ΄λ μͺ½μ μ±λ₯μ΄ λ μ’μκ°? : βμ μ μλ€β
𫧠DP 2 - μκ³ λ¦¬λ¬
- DP 1μ Mμ΄ nμ λΉν΄ ν° κ²½μ° μ¬μ¬μ©λμ§ μμ κ³μ°μ λ무 λ§μ΄ νλ€. μ€μ λ‘ κΌ νμν λ°°μ΄ μμλ§ κ³μ°ν μλ§ μλ€λ©΄!!
- $ K[i][w] $ λ₯Ό κ³μ°νλλ° $ K[i - 1][w] $ μ $ K[i - 1][w - W[i]] $ λΌλ μ΄μ νμ λ κ°λ§ νμ
- β΄ κ³μ°λ λ°°μ΄ μμλ€μ νμΈν ν κΌ νμν μμλ§ κ³μ°
@ KP_E
𫧠DP 2 - λΆμ
- κ°μ λ μκ³ λ¦¬μ¦μ 볡μ‘λ
- μ€μ κ³μ°λλ λ°°μ΄ μμμ μμ λΉλ‘
- $ K(n, M) $ μ ꡬνκΈ° μν΄ κ³μ°νλ λ°°μ΄ μμμ μλ νμ κ±°μ¬λ¬ μ¬λΌκ°λ©° μ΅λ 2λ°°μ© λμ΄λλ€κ³ ν λ $ \sum_{l = 1}^n 2^{l - 1} = 2^n - 1 $κ°: μ΅μ μ κ²½μ° $ Ζ(2^n) $
- κ·Έλ¬λ, μ μ₯λλ μμκ°―μλ λ°°μ΄ μμκ°―μλ³΄λ€ λ§μ μ μμ
- KP_Fμμ μΉ ν΄μ§ μμλ€μ΄ κ³μ° λμμ΄λΌ νλ€λ©΄ κ·Έ μ«μλ $ Ζ(nM) $
- λͺ¨λ 물건μ 무κ²κ° 1μ΄κ³ n β MμΌ κ²½μ°μ ν΄λΉ
- λ κ°μ§ κ΄μ μ€ μ 리ν κ±Έλ‘ μκ°νλ©΄ λλ―λ‘ $ O(minimum(2^n, nM)) $
- μ€μ κ³μ°λλ λ°°μ΄ μμμ μμ λΉλ‘
@ KP_F
𫧠DP 3 - μκ³ λ¦¬λ¬
- μ§κΈκΉμ§ μ΄ν΄λ³Έ λμ κ³νλ² μκ³ λ¦¬μ¦μ 물건 무κ²λ λ°°λ μ©λμ΄ μ€μμΈ κ²½μ°μλ μ¬μ© λΆκ°
- βμμΉμ μΆ©μ€νμβ
- μ΄μ° μ λ³΄μΈ μ μ λμ μ°μ μ λ³΄μΈ μ€μλ₯Ό μ²λ¦¬νλλ‘ κ°μ
- μ΄μ° μ 보λ₯Ό νννλ λκ΅¬μΈ λ°°μ΄ λμ μ°μ μ 보λ₯Ό νννλ λκ΅¬μΈ ν¨μμ μ΄μ
- βμμΉμ μΆ©μ€νμβ
- ν¨μ $ K(i, w) $ μ μν μ μ(revisited)
- @ KP_G
- μ λ ₯μΌλ‘ 물건과 λ°°λ 무κ²κ° μ£Όμ΄μ§λ©΄ μ μΌν μΆλ ₯κ°μΌλ‘ μ΅λ μ΄μ΅μ μμ±
- μ΄λ€ λͺ¨μ΅μ κ·Έλν? : μ λ ₯ λ³μκ° λμ΄λ―λ‘ 3μ°¨μ κ·Έλνλ‘ λνλ΄μ΄μΌ ν¨
- μ΄ν΄νκΈ° μ½λλ‘ $ K(i, w) $ λ₯Ό μ¬λ¬ 2μ°¨μ ν¨μλ‘ μͺΌκ°λ³΄μ
- $ i $ λ μ μ, $ w $ λ μ€μμ΄λ―λ‘ κ° $ i $ μ λν΄ μλ‘ λ€λ₯Έ ν¨μ $ K_i(w) $ λ₯Ό μ μνλ κ²μ΄ νλΉ
- $ K_i(w): { object_1, β¦, object_i } $ μ λν΄ $ x $ μΆμ λ°°λ 무κ²λ₯Ό, $ y $ μΆμ μ΅λ μ΄μ΅μ λνλ΄λ ν¨μ
- $ K_0(w), K_1(w), β¦, K_i(w), β¦, K_n(w) $ λ₯Ό μ μνλ κ²μ΄ κ°λ₯
- $ K_n(w) $ λ₯Ό ꡬν μ μλ€λ©΄ μ°λ¦¬κ° μνλ μ΅μ ν΄μΈ $ K_n(M) $ μ κ°μ κ³μ° κ°λ₯
- 0-1 λ°°λ λ¬Έμ μ μν μ μ ν¨μ $ K(i, w) $ λ₯Ό ν¨μ $ K_i(w) $ λ‘ μ¬μ μ
- @ KP_H
- $ K_0(w) = 0 $
- ν¨μ $ K_{i - 1}(w - w_i) + p_i $ λ $ K_{i - 1}(w) $ λ₯Ό $ x $ μΆμΌλ‘ $ w_i $ λ§νΌ, $ y $ μΆμΌλ‘ $ p_i $ λ§νΌ νν μ΄λν κ²
- 쑰건μ λ°λΌ $ K_{i - 1}(w - w_i) + p_i $ κ³Ό $ K_{i - 1}(w) $ λ₯Ό νλλ‘ ν©μΉλ©΄ $ K_i(w) $ λ₯Ό ꡬν μ μμ
- β μνμ κ·λ©λ²μ μν΄ $ K_n(w) $ λ₯Ό μ λ κ°λ₯
- $ K_0(w) = 0 $ μ΄λ€. μ΄λ₯Ό νν μ΄λνμ¬ $ K_0(w - w_1) + p_1 $ λ₯Ό ꡬν ν $ K_1(w) $ λ₯Ό μ»λλ€.
- $ K_1(w) $ λ₯Ό νν μ΄λνμ¬ $ K_1(w - w_2) + p_2 $ λ₯Ό ꡬν ν $ K_2(w) $ λ₯Ό μ»λλ€.
- β¦
- $ K_{i - 1}(w) $ λ₯Ό νν μ΄λνμ¬ $ K_{i - 1}(w - w_i) + p_i $ λ₯Ό ꡬν ν $ K_i(w) $ λ₯Ό μ»λλ€.
- β¦
- $ K_{n - 1}(w) $ λ₯Ό νν μ΄λνμ¬ $ K_{n - 1}(w - w_n) + p_n $ μ ꡬν ν $ K_{n}(w) $ λ₯Ό μ»λλ€.
@ U κΈ°λ§κ³ μ¬ μΆμ μμ : yμΆ νν μ΄λμΌλ‘ ꡬνλ λ°©λ²
@ KP_I
- μκ³ λ¦¬μ¦
- μ κ·Ό λ°©λ²: βμμΉμ μΆ©μ€νμβ
- μ°μ μ 보λ₯Ό νννλ λκ΅¬μΈ ν¨μλ₯Ό μ΄μ° μ 보λ₯Ό μ΄μ©νμ¬ νν
- κ° $ K_i(w) $ ν¨μμ κ·Έλνλ ꡬκ°μμλ§ μ°μμΈ κ³λ¨μμ νν
- λ°λΌμ κ° κ΅¬κ°μ μμμ μ’νλ₯Ό μμ 리μ€νΈλ‘ κ΄λ¦¬
- μ) [κ·Έλ¦Ό 4.15]μ (d)λ ꡬκ°μ΄ 2κ°μ΄λ―λ‘ μμμ μμ 리μ€νΈ $ {(5, 4), (8, 5)} $
- ν΅μ¬ μμ΄λμ΄: β $ K_{i - 1}(w) $ λ₯Ό νν μ΄λνμ¬ $ K_{i - 1}(w - w_i) + p_i $ λ₯Ό ꡬν ν $ K_i(w) $ λ₯Ό μ»λλ€.β
- $ S_{i - 1} : K_{i - 1}(w) $ μ μμμ 리μ€νΈ, $ SP_{i - 1} : K_{i - 1}(w - w_i) + p_i $ μ μμμ 리μ€νΈ
- λͺ©ν: $ S_0 $ μμλΆν° μΆλ°νμ¬ $ S_n $ μ ꡬνλ κ²
- 1) $ K_{i - 1}(w) $ λ₯Ό νν μ΄λνμ¬ $ K_{i - 1}(w - w_i) + p_i $ λ₯Ό ꡬνλ €λ©΄ $ S _{i - 1} $ μ κ° μ’νμ $ (w_i, p_i) $ λ₯Ό λν¨
- 2) $ K_{i - 1}(w) $ κ³Ό $ K_{i - 1}(w - w_i) + p_i $ λ₯Ό μ΄μ©νμ¬ $ K_i(w) $ λ₯Ό μ»μΌλ €λ©΄ $ S_{i - 1} $ μ $ SP_{i - 1} $ λ₯Ό ν©λ³νμ¬ $ S_i $ μμ±
- κΈ°λ³Έμ μΌλ‘ μ λ ¬λ 리μ€νΈλ₯Ό νλλ‘ ν©μΉλ μμ
- λ¨ ν©λ³ μ λ μμ (x1, y1), (x2, y2)μ¬μ΄μ x1 β₯x2μ΄κ³ y1 β€ y2μΈ κ΄κ³λΌλ©΄ (x1, y1) μ κ±°
@ KP_J
κ° ν¨μλ μ λ ¬λ μ μ 리μ€νΈ
μλλ μ΅λν λ§μ μ μ κΈ°μ΅ν΄μ μλ ν¨μμ λͺ¨μ΅μ κΈ°μ΅νλ κ²μ΄ μ’μλ°, κ²λ¨μ κ·Έλνλ₯Ό κ°μ§λ μ΄λ° μν©μμλ λ¨μν μ λͺ κ° λ§μ κΈ°μ΅νκ³ λ xμ λν y κ°μ μμλΌ μ μμ
κ° λ¬Όκ±΄μ λν΄μλ, κ° ν¨μμ 물건μ 무κ²μ κ°μΉλ₯Ό ννμ΄λν κ²μΌλ‘
κ·Έλ¦¬κ³ μ΄μ ν¨μμ νν μ΄λν ν¨μλ₯Ό νλμ 리μ€νΈλ‘ ν©μΉλ€, λ 리μ€νΈλ μ λ ¬λμ΄μλ€ (κ³λ¨μ) (μ λ ¬λ λ 리μ€νΈλ₯Ό νλλ‘ ν©νκΈ°? => ν©λ³ μ λ ¬)
κ° xμ yκ°μ λΉκ΅,
μ’ν Aμ Bμ λν΄, x yκ° λ λ€ μμ μ’νκ° κ·Έλνμ κ·Έλ €μ§κ³ ,
xλ y μ€ νλλ§ μμ κ²½μ°μλ, Aμ B μ€ xκ° λ ν° μͺ½μ μ λ ¬κ³Όμ μμ μ μΈκ° λλ€ (μλνλ©΄ xκ° λ μμ μͺ½μ΄ κ·Έ xλ³΄λ€ ν° κ°λ μ€λͺ
ν μ μμΌλκΉ)
$ S_0 $, ννμ΄λ $ SP_0 $,
ν©μΉκ³ $ S_1 $, ννμ΄λ $ SP_1 $,
π« Solve By BackTracking
- $ p_i/w_i > p_{i + 1}/w_{i + 1} $
BTμμλ μμ λ΄λ¦Όμ°¨μ μ λ ¬ μ‘°κ±΄μ΄ λΆμ
Backtracking μ΅μ ν λ¬Έμ ν΄κ²°μ μν ꡬ쑰 (λ§ν¬ μ°Έκ³ )
𫧠μν κ³΅κ° νΈλ¦¬
- μ£Όμ λ³μ
weight
= νμ¬κΉμ§ λ΄μ 물건μ λ¬΄κ² ν©profit
= νμ¬κΉμ§ λ΄μ 물건μ μ΄μ΅ ν©max_profit
(optimal) = νμ¬κΉμ§μ μ΅μ ν΄ μ¦ νμ¬κΉμ§μ μ΅λ μ΄μ΅
- μ΅μ ν΄λ₯Ό λ³κ²½νλ 쑰건
- λ°°λμ 물건μ λ£μ΄μΌ νλ λ
Έλλ₯Ό λ°©λ¬Έ β
weight
μprofit
μ κ°μ΄ μ¦κ° - λ°°λμ μ©λμ λμ΄μμ§ μμΌλ©΄μ μ§κΈκΉμ§μ μ΅λ μ΄μ΅λ³΄λ€ ν° μ΄μ΅μ΄ λ°μνλ©΄
max_profit
κ°μ λ³κ²½λprofit
κ°μΌλ‘ λ°λμ΄μΌ ν¨ - λ°λΌμ λ€μ 쑰건μ λ§μ‘±νλ©΄ μ΅μ ν΄κ° λ³κ²½
- $ (weight \le M) ^(and) (profit > max\ profit) $
- λ°°λμ 물건μ λ£μ΄μΌ νλ λ
Έλλ₯Ό λ°©λ¬Έ β
@ TODO : and κΈ°νΈ
𫧠BT - μκ³ λ¦¬λ¬
- μ λ§νμ§ μμ λ
Έλμ νλ³(νμ¬ iλ²μ§Έ 물건κΉμ§ κ²°μ λ μν)
- κ·μΉ 1) λ μ΄μ 물건μ λ΄μ μ μλ κ²½μ°, $ weight \ge M $
- κ·μΉ 2) μμ§μ λ°°λμ μ¬μ κ° μμ§λ§ ν μνμμ μ΄λ»κ² μ§ννλλΌλ νμ¬κΉμ§μ μ΅λ μ΄μ΅λ³΄λ€ λ ν° μ΄μ΅μ κΈ°λνμ§ λͺ»νλ κ²½μ°(νμ¬κΉμ§ λ΄μ 물건μ μ΄μ΅μλ€κ° λ¨μμλ 물건λ€μ μ΅μ μΌλ‘ μΆκ°νμ¬ μ»μ μ μλ μ΄μ΅μ ν©νλ€ νλλΌλ νμ¬κΉμ§μ μ΅λ μ΄μ΅μ λ₯κ°νμ§ λͺ»νλ κ²½μ°)
- λΆλΆ λ°°λ λ¬Έμ λ‘ νμμ λμ μ΅λ μ΄μ΅ >= 0-1 λ°°λ λ¬Έμ λ‘ νμμ λμ μ΅λ μ΄μ΅
- β΄ μ΅λ μ΄μ΅μ μνμ ꡬνκΈ° μν΄ λΆλΆ λ°°λ λ¬Έμ λ‘ λ³μ
- νμ¬κΉμ§ λ΄μ 물건μ μ΄μ΅($ profit $) + λ¨μ 물건μ λμμΌλ‘ λΆλΆ λ°°λ λ¬Έμ λ‘ μ ννμ¬ νμμ λμ μ΅λ μ΄μ΅($ exp\ profit $)μ΄ νμ¬κΉμ§μ μ΅λ μ΄μ΅($max\ profit$)λ³΄λ€ μλ€λ©΄ μ λλ‘ μ λ§ν μκ° μμ β μ²μμ 물건μ λ¨μ λ¬΄κ² λΉ μ΄μ΅μ μμ λ°λΌ λ΄λ¦Όμ°¨μμΌλ‘ μ λ ¬ν μ΄μ
- $ profit + exp\ profit \ge max\ profit $
- @ λ°°λ 0001
- λΆλΆ λ°°λ λ¬Έμ λ‘ νμμ λμ μ΅λ μ΄μ΅ >= 0-1 λ°°λ λ¬Έμ λ‘ νμμ λμ μ΅λ μ΄μ΅
@ KP_0000
@ KP_0001
Back-Tracking, μ€μ λ‘ νΈλ¦¬λ₯Ό λ§λ€μ§λ μκ³ , κ° λ 벨μ ν΄λΉνλ μν μ 보λ₯Ό λ°°μ΄μ μ μ₯νλ€.
- λ°°μ΄μ μ΄μ©νμ¬ μν κ³΅κ° νΈλ¦¬λ₯Ό κ΄λ¦¬νλ λ°©λ²
- λΆλΆ μ§ν©μ ν© λ¬Έμ μ λμΌ
- κΈ°μ΅ν΄μΌ ν μ 보λ βκ±Έμ΄μ¨ κΈΈβ
- λ 벨 i λ
Έλλ i κ° λ¬Όκ±΄κ°μ΄λ° λ°°λμ λ£μ 물건λ€μ κΈ°μ΅ν΄μΌ ν¨
- ν΄λΉ λ Έλκ° μ λ§νμ¬ μμ λ Έλλ‘ λ΄λ €κ°λ€λ©΄ i+1κ° λ¬Όκ±΄κ°μ΄λ° λ°°λμ λ£μ 물건λ€μ κΈ°μ΅
- μ λ§νμ§ μμ λΆλͺ¨ λ Έλλ‘ λ°±νΈλνΉνλ€λ©΄ i -1κ° λ¬Όκ±΄κ°μ΄λ° λ°°λμ λ£μ 물건λ€μ κΈ°μ΅
μΈλ±μ€ | 1 | 2 | 3 | 4 |
ν¬ν¨μ¬λΆ | false | true | true | - |
λ¨λ§ λ Έλκ° μλ λ Έλκ° ν΄λ΅μ΄λΌλ©΄ ν΄λ΅ λ Έλμ λ 벨κΉμ§ μ μ₯λ κ°λ§μ΄ μ ν¨
- λ°°μ΄ μΈλ±μ€ : 물건
- λ°°μ΄ κ°: 물건μ ν¬ν¨ μ¬λΆ
β΄ n κ°μ κ°(true/false)μ μ μ₯ν μ μλ 1μ°¨μ λ°°μ΄μ΄ νμ
𫧠BT - ꡬν
_01_ks_BT(0,0,0)
μ νΈμΆν¨μΌλ‘μ¨ μμ
μ μ λ³μ max_profit
μ μ΄κΈ°κ°μ 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void _01_ks_BT(int i, int profit, int weight)
{
if (weight <= M && profit > max_profit)
{
max_profit = profit; // μ΅λ μ΄μ΅μ λ³κ²½
optimal = (X[1]..X[i]); // i κ°μ 물건λ€μ ν¬ν¨ μ¬λΆ
}
if (Promising(i, profit, weight))
{
X[i + 1] = true;
_01_ks_BT(i + 1, profit + P[i + 1], weight + W[i + 1]);
X[i + 1] = false;
_01_ks_BT(i + 1, profit, weight);
}
}
bool Promising(int i, int profit, int weight)
{
int k, exp_weight = 0;
float exp_profit = 0;
// κ½ μ°¨κ±°λ μ°’μ΄μ§
if (weight >= M)
return false;
for (k = i + 1; k <= n; k++)
{
if (weight + exp_weight + W[k] > M)
break;
exp_weight += W[k];
exp_profit += P[k];
}
if (k <= n)
exp_profit += (M - (weight + exp_weight)) * P[k] / W[k];
if (profit + exp_profit <= max_profit)
return false;
return true;
}
𫧠BT - λΆμ
μν κ³΅κ° νΈλ¦¬μ λ Έλ μ
\[1 + 2 + 2^2 + β¦ + 2^n = 2^{n+1} - 1\]λΆλΆμ§ν©μ ν© λ¬Έμ μ μν κ³΅κ° νΈλ¦¬κ° λμΌ
NP-μμ λ¬Έμ μ€μλ λΉκ΅μ λ
Έλμκ° μ μ§λ§ μ¬μ ν μ§μ 볡μ‘λ
μ λ§ν λ Έλ μ
- μ λ§ν λ Έλ κ°μλ₯Ό κ³μ°ν μ μμ
- κ°μ κ°μμ λ Έλλ₯Ό κ°λλΌλ λ°°λ μ©λμ΄λ 물건 무κ²μ λ°λΌ μ λ§ν λ Έλμ μκ° λ¬λΌμ§
- μ΅μ ν λ¬Έμ β μν κ³΅κ° νΈλ¦¬λ₯Ό λͺ¨λ λ€μ ΈμΌ ν¨. λ¨μ§ νμνλ λ Έλμ μκ° λ¬λΌμ§ λΏ
λμ κ³νλ² vs. λ°±νΈλνΉ
- Horowitzμ Sahniμ λͺ
μ βFundamentals of Computer Algorithmsβμλ Venkateshκ° μ€μ μ»΄ν¨ν°μμμ μ€νμμΌ λ³Έ κ²°κ³Όκ° μλ‘: λ€μ 4κ°μ§ κ²½μ°μ λ°μ΄ν° μ§ν© μ¬μ©
- β κ° λ¬Όκ±΄μ 무κ²μ μ΄μ΅μ 1~1,000 λ²μ μμμ μμλ‘ μμ±ν κ²½μ°
- β κ° λ¬Όκ±΄μ 무κ²μ μ΄μ΅μ 1~100 λ²μ μμμ μμλ‘ μμ±ν κ²½μ°
- β κ° λ¬Όκ±΄ 무κ²λ₯Ό 1~100 λ²μ μμμ μμλ‘ μμ±νκ³ μ΄μ΅μ 무κ²μ 10μ λν κ²½μ°
- β κ° λ¬Όκ±΄ 무κ²λ₯Ό 1~100 λ²μ μμμ μμλ‘ μμ±νκ³ μ΄μ΅μ 무κ²μ 1.1μ κ³±ν κ²½μ°
- λ°°λ μ©λ Mμ 물건 무κ²μ ν©μ μ λ°μ΄ λλλ‘ νκ³ λ¬Όκ±΄μ κ°μ nμ λν΄ 10κ°μ©μ μΈμ€ν΄μ€μ λν μΈ‘μ κ°μ λΉκ΅ β μΌλ°μ μΌλ‘ λ°±νΈλνΉ μκ³ λ¦¬μ¦μ΄ λμ κ³νλ² μκ³ λ¦¬μ¦λ³΄λ€ μ°μ