Two versions of the problem
- 0-1 knapsack problem
- Items are indivisible: you either take an item or not ➡️ DP (Greedy X)
- Fractional knapsack problem
- Items are divisible: you can take any fraction of an item ➡️ Greedy
- compute the value per pound vi/wi for each item
- For greedy strategy, the thief begins by taking as much as possible of the item with the greatest value per pound, continue
➡️ Both problem optrmal substructure property, but ony fractronal greedy choice property
0-1 knapsack problem![](https://velog.velcdn.com/images/choihjin/post/15abdc18-c8f2-48df-b98b-23d030abb1af/image.png)
[1] Brute force approach
- Since there are n items, there are 2n possible combinations of items
- We go through(살펴보다) all combinations and find the one with the most total value and with total weight less or equal to W
- Running time will be Θ(2n)
[2] Greedy
: does not work for this problem
[3] Dynamic programming
- identifying the subproblems is important
- If items are labeled 1..n, Sk = { items labeled 1, 2, .. k } ➡️ 가장 간단한 방법
- This is a valid subproblem definition
- Q. Can we describe the final solution (Sn) in terms of subproblems (Sk)?
- A. Unfortunately, we can't do that
![](https://velog.velcdn.com/images/choihjin/post/ef822bb0-46cf-412c-b306-86c523752106/image.png)
- So current definition of a subproblem is flawed(결함이 있다) and we need another one!
- Add another parameter: w, which will represent the exact weight for each subset of items
- The subproblem then will be B[k,w]
![](https://velog.velcdn.com/images/choihjin/post/fbf9486f-85b3-4158-8c05-46b7e99474f1/image.png)
- The best subset of Sk that has the total weight W, either contains item k or not (k를 넣을지 말지)
- First case: wk > W. Item k can’t be part of the solution
- Second case: wk <= W. Item k may be in the solution, and we choose the case with greater value
for w = 0 to W
B[0, w] = 0
for i = 1 to n
B[i, 0] = 0
for w = 1 to W
if w[i] <= W
if b[i] + B[i -1 , W - w[i]] > B[i - 1, W]
B[i, w] = b[i] + B[i - 1, W - w[i]]
else B[i, w] = B[i-1, w]
else B[i, W] = B[i - 1, W]
⭐️ O(nW)
[4] Branch and Bound - Best First Search
-
We do not visit every node, but determine if it is worth(값어치 있는) or not
-
전제 조건 : Sorting in descending order according to bi / wi (benefit per weight)
-
At each node we compute three local values
- benefit : sum of benefit value up to this node
- weight : sum of weights up to this node
- bound : upper bound on the benefit we could achieve by expanding beyond this node (predict, foresee, forecast)
-
Computing bound
- tot_weight = weight(이미 knapsack에 넣은 총 weight) + 미래에 넣을 weight ( tot_weight <= W )
![](https://velog.velcdn.com/images/choihjin/post/02608a33-66c2-4d80-a6b0-aa7b11b402fa/image.png)
![](https://velog.velcdn.com/images/choihjin/post/ca41e9f2-b1f1-4a64-a36a-6efe6172800a/image.png)
-
And we need one more global variable max_benefit
: benefit in the best solution found so far
- Initially, max_benefit = 0
- if weight < W, max_benefit = max(max_benefit, benefit)
- Q. Relationship between local variable ‘bound’ and global variable ‘max_beneit’?
- promising : expand beyond this node
- nonpromising : stop here
- if bound ≤ max_benefit or weight > W ➡️ nonpromising
- if bound > max_benefit and weight ≤ W ➡️ promising
-
Two non-promising case
- Case 1: bound ≤ max_benefit
- The ‘benefit’ computed at this node is effective
- We just do not expand beyond this node (필요가 없다)
- Case 2: weight > W
- The ‘benefit’ computed at this node is not effective
- So ‘max_benefit’ will not be updated and we do not expand beyond this node
-
Basically apply BFS and choose promising(유망한) and unexpanded node with greatest bound
-
Ex_![](https://velog.velcdn.com/images/choihjin/post/ac137b87-055e-4cd3-bd6b-aacc787e8083/image.png)
![](https://velog.velcdn.com/images/choihjin/post/ad49e697-4b46-49da-ac47-b10ea90e5949/image.png)
![](https://velog.velcdn.com/images/choihjin/post/a3c37d44-a7df-4de5-bb27-272ea5fa99d4/image.png)
![](https://velog.velcdn.com/images/choihjin/post/6258b0c3-96aa-46dd-93bf-65300b777449/image.png)
![](https://velog.velcdn.com/images/choihjin/post/469f1043-951f-447d-ac52-bddf42a96b2a/image.png)
![](https://velog.velcdn.com/images/choihjin/post/48b3f391-1065-45a2-a49a-9be110bb7b84/image.png)
![](https://velog.velcdn.com/images/choihjin/post/a220086b-94af-4468-82ed-9b14b27675b3/image.png)
![](https://velog.velcdn.com/images/choihjin/post/94fb1363-334d-4862-998e-065b965ea4e3/image.png)
Exercise in class
1. Knapsack Greedy
Find running time
➡️ θ(n lg n) : sortingθ(n lg n) + 1부터 n-1까지 스캔θ(n)
➕ merge, heap sort만 θ(n lg n)
2. Knapsack DP
n = 4
W = 4
Elements(w, b) : (2, 3), (3, 4), (4, 5), (5, 6)![](https://velog.velcdn.com/images/choihjin/post/5a64be91-4990-4e0f-986d-a9536be082c0/image.png)
➕ DP는 sorting 필요x, Greedy는 필요!
3. Knapsack BB
Total_weight = 10
i | bi | wi | bi / wi |
---|
1 | 30 | 2 | 15 |
2 | 60 | 5 | 12 |
3 | 70 | 7 | 10 |
4 | 20 | 4 | 5 |
➡️ sorted with bi / wi DES![](https://velog.velcdn.com/images/choihjin/post/085868fb-c317-45cd-a3f2-7c7671c75d9a/image.jpeg)
HGU 전산전자공학부 용환기 교수님의 23-1 알고리듬 분석 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.