π Subset Sum Problem
π« Subset Sum Problem (Sum of Subsets Problem)
λΆλΆμ§ν©μ ν© λ¬Έμ
μ νκ°μ μ μλ₯Ό μμλ‘ νλ μ§ν©μ΄ μμ λ μμμ ν©μ΄ 0μ΄ λλ λΆλΆμ§ν©μ΄ μ‘΄μ¬νλμ§ μμλ΄λ λ¬Έμ (λ¨ κ³΅μ§ν©μ μ μΈ)
i.e. μ§ν©{-4, -2, 1, 3}μ κ²½μ° λΆλΆμ§ν© {-4, 1, 3}μ μμ ν©μ΄ 0
μμ ν©μ κ΄ν 쑰건μ μμμ μ μλ‘ μΌλ°ν κ°λ₯ (ν© 0 β ν© n)
물건μ λ¨μ 무κ²λΉ μ΄μ΅μ΄ λμΌν 0-1 λ°°λ λ¬Έμ
0-1 λ°°λ λ¬Έμ μμ μ΅λ μ΄μ΅μ λ°°λ μ©λ Mμ κ½ μ±μΈ κ²½μ° = μμλ₯Ό μμλ‘ νμ νλ λΆλΆμ§ν©μ ν© λ¬Έμ μ λμΌ
@ μλ£ Subset0000
@ μ£Όμ : wi < wi+1
κ° λ¬Όκ±΄μ μ΄μ΅μ λν μ 보λ λ μ΄μ νμ μμ
μ£Όμ : 물건μ 무κ²μ λ°λΌ μ€λ¦μ°¨μμΌλ‘ μ λ ¬
@ λ¬΄κ² Mμ΄ κΌ 0μ΄ μλμ¬λ λ¨ (μμμ μ μλ‘ μΌλ°ν κ°λ₯)
@ SSP_0000
π« Solve By BackTracking
𫧠μν κ³΅κ° νΈλ¦¬
N-Queen, K-Graph-Coloringκ³Ό λ€λ₯΄κ², λ Έλμ μμΉ μ λ³΄κ° μ μ₯λλ κ²μ΄ μλκ³ , κ° λ Έλ κΈ°μ€ λ¬΄κ²κ° μ μ₯λ¨
𫧠μκ³ λ¦¬λ¬
- λ 벨
i
μ λ Έλκ° μ λ§νμ§ μμμ νλ³νλ κΈ°μ€- νμ¬
i
λ²μ§Έ 물건κΉμ§ κ²°μ λ μνμ΄κ³ νμ¬κΉμ§ λ°°λμ λ£μ 물건λ€μ 무κ²μ ν©μweight
λΌ νλ©΄ λ€μ κ²½μ°μ μ λ§νμ§ μμ λ Έλ - κ·μΉ 1) νμ¬κΉμ§μ 무κ²κ° λ°°λμ 무κ²λ₯Ό μ΄κ³Ό: $weight + rest > M$
- κ·μΉ 2) μμ§μ λ°°λμ μ¬μ κ° μμ§λ§ μ΄λ€ 물건μ μΆκ°λ‘ λ£λλΌλ μ΄κ³Ό
- $weight + w_{i+1} > M$
- 물건μ 무κ²μ λ°λΌ μ€λ¦μ°¨μμΌλ‘ μ λ ¬ν μ΄μ
- κ·μΉ 2λ₯Ό μ‘°μ¬νμ¬ κ°μ§μΉκΈ°λ₯Ό νκ² λλ©΄ κ·μΉ 1μ μν μ λ§νμ§ μμ κ²½μ°λ μ λλ‘ λ°μ λΆκ°λ₯ β κ·μΉ 1μ κ²μ¬ν νμ μμ
- κ·μΉ 3) λ¨μ 물건μ λͺ¨λ λ°°λμ λ£μ΄λ λ°°λ μ©λμ λ―ΈμΉμ§ λͺ»ν¨
- λ¨μ 물건λ€μ λ¬΄κ² ν©μ
rest
λΌ ν λ, $weight + rest < M$
- λ¨μ 물건λ€μ λ¬΄κ² ν©μ
- νμ¬
@ SSP_0001
- λ°°μ΄μ μ΄μ©νμ¬ μν κ³΅κ° νΈλ¦¬λ₯Ό κ΄λ¦¬νλ λ°©λ²
- κΈ°μ΅ν΄μΌ ν μ 보λ βκ±Έμ΄μ¨ κΈΈβ
- λ 벨
i
λ Έλλi
κ° λ¬Όκ±΄κ°μ΄λ° λ°°λμ λ£μ 물건λ€μ κΈ°μ΅ν΄μΌ ν¨- ν΄λΉ λ
Έλκ° μ λ§νμ¬ μμ λ
Έλλ‘ λ΄λ €κ°λ€λ©΄, λ€μ λ¨κ³μ
i + 1
κ° λ¬Όκ±΄ κ°μ΄λ° λ°°λμ λ£μ 물건λ€μ κΈ°μ΅ - ν΄λΉ λ
Έλκ° μ λ§νμ§ μμ λΆλͺ¨ λ
Έλλ‘ λλμκ°λ€λ©΄, λ€μ λ¨κ³μ
i - 1
κ° λ¬Όκ±΄ κ°μ΄λ° λ°°λμ λ£μ 물건λ€μ κΈ°μ΅
- ν΄λΉ λ
Έλκ° μ λ§νμ¬ μμ λ
Έλλ‘ λ΄λ €κ°λ€λ©΄, λ€μ λ¨κ³μ
μΈλ±μ€ | 1 | 2 | 3 | 4 |
ν¬ν¨μ¬λΆ | fales | true | false | true |
λ¨λ§ λ Έλκ° μλ λ Έλκ° ν΄λ΅μ΄λΌλ©΄ ν΄λ΅ λ Έλμ λ 벨κΉμ§ μ μ₯λ κ°λ§μ΄ μ ν¨
- λ°°μ΄ μΈλ±μ€ : 물건
- λ°°μ΄ κ°: 물건μ ν¬ν¨ μ¬λΆ
β΄ n κ°μ κ°(true/false)μμ μ μ₯ν μ μλ 1μ°¨μ λ°°μ΄μ΄ νμ
𫧠ꡬν
SumOfSubsetsBT(0, 0, rest)
λ₯Ό νΈμΆν¨μΌλ‘μ¨,
μμ λ³μ rest
μ μ΄κΈ° κ°μ λͺ¨λ 물건μ λ¬΄κ² ν© = λ°°μ΄ W[ ]
μ κ°μ λͺ¨λ λν κ°
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
void SumOfSubsetsBT(int i, int weight, int rest)
{
if (!Promising(i, weight, rest)) // μ λ§νμ§ μμΌλ©΄ ν¨μ€
return;
if (weight == M) // μ°ΎμΌλ©΄ μ¦μ λ (κ²°μ λ¬Έμ )
{
OutputSolution(i);
Exit(); // λμΆ© λλλ ν¨μ
}
else
{
// μΌμͺ½, μ€λ₯Έμͺ½ λ κ°μ λ
Έλλ§ λ³΄λ©΄ λ¨ (μ΄μ§νΈλ¦¬)
X[i + 1] = true;
SumOfSubsetsBT(i + 1, weight + W[i + 1], rest - W[i + 1]);
X[i + 1] = false;
SumOfSubsetsBT(i + 1, weight, rest - W[i + 1]);
}
}
bool Promising(int i, int weight, int rest)
{
// μ λ§νμ§ μμ κ²½μ°
// 1. λ¨μ κ±Έ λ€ λν΄λ λͺ©ν 무κ²μ 'λλ¬'ν μ μμ (λ ν΄μ γ·γ·)
// 2. 무κ²κ° λμΉ¨
if (weight + rest < M)
return false;
// (weight == M) β ν΄λ΅
if ((weight != M) && (weight + W[i + 1] > M))
return false;
return true;
}
𫧠λΆμ
μν κ³΅κ° νΈλ¦¬μ λ Έλ μ
\[1 + 2 + 2^1 + ... + 2^n = 2^{n+1} - 1\]2-κ·Έλν μ±μ λ¬Έμ μ κ°μ λ
Έλμ
NP-μμ λ¬Έμ μ€μλ λΉκ΅μ λ
Έλμκ° μ μ§λ§ μ¬μ ν μ§μ 볡μ‘λ
μ λ§ν λ Έλ μ
- ν΄λ°ν΄ μ¬μ΄ν΄ λ¬Έμ μ²λΌ μ λ§ν λ Έλ κ°μλ₯Ό κ³μ°ν μ μμ
- κ°μ κ°μμ μ μ μ΄λΌ νλλΌλ λ°°λ μ©λμ΄λ 물건 무κ²μ λ°λΌ μ λ§ν λ Έλμ μκ° λ¬λΌμ§
- μμ£Ό 빨리 ν΄λ΅μ μ»μ μλ μκ³ μν κ³΅κ° νΈλ¦¬λ₯Ό λͺ¨λ λ€μ ΈμΌ ν μλ μμ
- κ°μ₯ λ¬΄κ±°μ΄ λ¬Όκ±΄μ μ μΈν λλ¨Έμ§ λ¬Όκ±΄λ€μ λ¬΄κ² ν©μ΄ λ°°λμ μ©λλ³΄λ€ μκ³ , κ°μ₯ λ¬΄κ±°μ΄ λ¬Όκ±΄μ 무κ²κ° λ°°λμ μ©λκ³Ό κ°λ€λ©΄ ν΄λ΅μ μ°ΎκΈ° μν΄ λͺ¨λ λ Έλλ₯Ό νμνμ¬μΌ ν¨