Table of content
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
I. STATEMENT
Taking about the problem
Problem: During midnight, a thief breaks into a jewelry shop. There are $$$N$$$ priceful items whose value and weight are known. The item $$$p$$$ can be sold for $$$V_p$$$ money but having $$$C_p$$$ weight. There is a bag with infinity amount of space, means that any item can be pinto it while the item's value in the bag remain unchanged ! But, it can only hold maximumly $$$W$$$ weight.
Question: What is the value $$$V$$$ that the thief can steal from the shop.
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
II. EXAMPLE
To understand the problem better
- Input
3 8
2 10
4 20
6 30
- Output
40
- Explanation:
There are 8 possible cases
{} -> 0 value, 0 weight
{1} -> 10 value, 2 weight
{2} -> 20 value, 4 weight
{3} -> 30 value, 6 weight
{1, 2} -> 30 value, 6 weight
{1, 3} -> 40 value, 8 weight - optimal
{2, 3} -> 50 value, 10 weight - invalid weight
{1, 2, 3} -> 60 value, 12 weight - invalid weight
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
III. Solution for small number of element — N
How much will you get in each possible subset ?
A. Permutation Approach (Bad) — $$$O(n!)$$$ time — $$$O(n)$$$ space
For each possible permutation, pick elements until it weight too much
The result is the maximum value sum, for which weight sum is not greater than $$$W$$$
B. Bitmasking Approach (Good) — $$$O(2^n)$$$ time — $$$O(n)$$$ space
Because the order isnt important, we just need to test all every possible subset
The result is the maximum value sum, for which weight sum is not greater than $$$W$$$
C. Meet-in-the-middle Approach (Better) — $$$O(2^{n/2})$$$ time — $$$O(2^{n/2})$$$ space
Split the array into two halves $$$L$$$ and $$$R$$$. In each half, we will calculate every possible subsets. And in each subset we store a pair of $$$(value\ sum, weight\ sum)$$$
For each element $$$X(value_X, weight_X) \in L$$$, we need to find suitable element $$$Y(value_Y, weight_Y) \in R$$$ that satisfying maximum $$$value_R$$$ and $$$weight_L + weight_R \leq W$$$
Therefore, we can sort all the $$$R$$$ set by increasing weight. Let $$$maxval_Y = max(value_E | E \in R, weight_E \leq weight_Y)$$$. Then for each $$$X \in L$$$, we can find its suitable $$$Y$$$ by binary search in $$$O(log\ |R|)$$$ with $$$O(|R|)$$$ precalculation
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
IV. Solution for small sum of weight — C[i]
What is the maximum value possible when your bag is exact $$$W$$$ weight ?
A) Recursive Dynamic Programming — $$$O(N \times W)$$$ time — $$$O(N \times W)$$$ space
Memorization:
f[i][s] = magic(int i, int s)stand for using from the $$$ith$$$ items, with the total weight of $$$s$$$ that maximum value is $$$f[i][s]$$$
- All $$$f[i][s]$$$ init as $$$-1$$$
Base cases
- If ($$$s > w$$$) then $$$v = -oo$$$ since we use more than what the bag can hold
- If ($$$i \geq n$$$) then $$$v = 0$$$ since there is no available item, so no weight added into the bag
Transistion
- Using current item, it will be $$$A = magic(i + 1, s + c_i) + v_i)$$$ — move to next item, weight is added with $$$c_i$$$, value is increased by $$$v_i$$$
- Not using current item, it will be $$$B = magic(i + 1, s + 0) + 0)$$$ — move to next item, weight is remained, value is not increased
- We want the maximum value so $$$magic(int\ i, int\ s) = max(A, B)$$$
The final result: $$$result = magic(1, 0)$$$ — starting from first item with $$$0$$$ weighted bag
B) Iterative Dynamic Programming — $$$O(N \times W)$$$ time — $$$O(N \times W)$$$ space
Memorization:
f[i][s]stand for using from the $$$ith$$$ items, with the total weight exact $$$s$$$ that maximum value is $$$f[i][s]$$$
- All $$$f[i][s]$$$ init as $$$0$$$ not $$$-1$$$
Base cases:
- $$$\forall x \geq 0, f[0][x] = 0$$$ — using no item, hence return no value
- $$$\forall x \geq 0, f[x][0] = 0$$$ — having no weight, hence no using item
- $$$\forall x > 0, y < 0, f[x][y] = -oo$$$ — define it as negative infinity for easier calculation
Transistion:
- Using current item, $$$A = \underset{0 \leq t + c_i \leq s}{\underset{j \leq i}{max}}(f[j][t]) + v[i] = \underset{0 \leq t = s - c_i}{\underset{j \leq i}{max}}(f[j][t]) + v[i] = \underset{0 \leq t = s - c_i}{\underset{j = i - 1}{f[j][t]}} + v[i]$$$ maximum value among all previous bags added to current item
- Not using current item, it will be $$$B = \underset{0 \leq t + 0 \leq s}{\underset{j \leq i}{max}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j \leq i}{max}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j = i - 1}{f[j][t]}} + 0$$$ — move to next item, weight is remained, value is not increased
- We want the maximum value so $$$f[i][s] = max(A, B) = max(f[i - 1][s], f[i - 1][s - c_i] + v_i)$$$
The final result: $$$result = \underset{0 \leq s \leq w}{max}(f[n][s])$$$ — starting from first item with $$$0$$$ weighted bag
C) Recursive Dynamic Programming (Space optimization) — $$$O(N \times W)$$$ time — $$$O(N + W)$$$ space
A) O(2W) DP space
Observe: $$$\forall i > 0, f[i][x]$$$ depends on $$$f[i - 1]$$$ and $$$f[i]$$$ only, hence we just need 2 dp array space
Define: When we calculate at pth element, we have $$$\underset{x \equiv p (mod 2)}{f[x]}$$$ is current dp array, $$$\underset{y \equiv p + 1 (mod 2)}{f[y]}$$$ is previous dp array
Transistion: $$$f[i][s] = max(f[i - 1][s], f[i - 1][s - c_i] + v_i)$$$ equivalent to $$$f[x][s] = max(f[y][s], f[y][s - c_i] + v_i)$$$
B) O(W) 1D — DP space
- From the above algorithm, we can change the inner loop
- Kinda tricky, but we only need one array, for each query $$$f[s]$$$ stand for maximum value with bag of weight $$$s$$$ upto that query.
- Notice that it is required for the second-inner-loop to iterate from $$$w$$$ downto $$$c_i$$$. Here is the reason
- Finally, here is 1D Dynamic Programming Solution
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
V. Solution for small sum of value — V[i]
What is the minimum bag weight possible when it is exact $$$S$$$ sum value ?
A) Recursive Dynamic Programming — $$$O(N \times SUM)$$$ time — $$$O(N \times SUM)$$$ space
Memorization:
f[i][s] = magic(int i, int s)stand for using from the $$$ith$$$ items, with the total value of $$$s$$$ that minimum weight is exact $$$f[i][s]$$$
- All $$$f[i][s]$$$ init as $$$-1$$$
Base cases
- If ($$$s < 0$$$) then $$$v = +oo$$$ means we use more value than expected
- If ($$$i > n$$$ and $$$s \neq 0$$$) then $$$v = +oo$$$ means there is currently no bag of exact $$$s$$$ value
- If ($$$i > n$$$ and $$$s = 0$$$) then $$$v = 0$$$ means there is actually a bag of exact $$$s$$$ value
Transistion
- Using current item, it will be $$$A = magic(i + 1, s - v_i) + c_i)$$$ — move to next item, sum value is reduce by $$$v_i$$$, weight is added with $$$c_i$$$
- Not using current item, it will be $$$B = magic(i + 1, s - 0) + 0)$$$ — move to next item, sum value is remained, weight is not increased
- We want the minimum weight so $$$magic(int\ i, int\ s) = min(A, B)$$$
The final result: $$$result = \underset{0 \leq s \leq \Sigma(v_i)}{max}(s | magic(1, s) \leq w)$$$ — maximum value whose weight is not greater than $$$W$$$
B) Iterative Dynamic Programming — $$$O(N \times SUM)$$$ time — $$$O(N \times SUM)$$$ space
Memorization:
f[i][s]stand for using from the $$$ith$$$ items, with the total value of exact $$$s$$$ that maximum value is $$$f[i][s]$$$
- All $$$f[i][s]$$$ init as $$$+oo$$$ not $$$-1$$$
Base cases:
- $$$\forall x \geq 0, f[0][x] = 0$$$ — using no item, hence return no weight
- $$$\forall x \geq 0, f[x][0] = 0$$$ — having no value, hence no using item
- $$$\forall x > 0, y < 0, f[x][y] = +oo$$$ — define it as negative infinity for easier calculation
Transistion:
- Using current item, $$$A = \underset{0 \leq t + v_i \leq s}{\underset{j \leq i}{min}}(f[j][t]) + c[i] = \underset{0 \leq t = s - v_i}{\underset{j \leq i}{min}}(f[j][t]) + c[i] = \underset{0 \leq t = s - c_i}{\underset{j = i - 1}{f[j][t]}} + v[i]$$$ minimum weight among all previous bags added to current item
- Not using current item, it will be $$$B = \underset{0 \leq t + 0 \leq s}{\underset{j \leq i}{min}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j \leq i}{min}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j = i - 1}{f[j][t]}} + 0$$$ — move to next item, value is remained, weight is not increased
- We want the minimum weight so $$$f[i][s] = min(A, B) = min(f[i - 1][s], f[i - 1][s - v_i] + c_i)$$$
The final result: $$$result = \underset{0 \leq s \leq \Sigma(v_i)}{max}(s | f[n][s] \leq w)$$$ — maximum value whose weight is not greater than $$$W$$$
C) Iterative Dynamic Programming (Space Optimization) — $$$O(N \times SUM)$$$ time — $$$O(N + SUM)$$$ space
A) O(2SUM) DP space
Observe: $$$\forall i > 0, f[i][x]$$$ depends on $$$f[i - 1]$$$ and $$$f[i]$$$ only, hence we just need 2 dp array space
Define: When we calculate at pth element, we have $$$\underset{x \equiv p (mod 2)}{f[x]}$$$ is current dp array, $$$\underset{y \equiv p + 1 (mod 2)}{f[y]}$$$ is previous dp array
Transistion: $$$f[i][s] = min(f[i - 1][s], f[i - 1][s - v_i] + c_i)$$$ equivalent to $$$f[x][s] = min(f[y][s], f[y][s - v_i] + c_i)$$$
B) O(SUM) 1D — DP space
- From the above algorithm, we can change the inner loop
- Kinda tricky, but we only need one array, for each query $$$f[s]$$$ stand for maximum value with bag of weight $$$s$$$ upto that query.
- Notice that it is required for the second-inner-loop to iterate from $$$sum$$$ downto $$$v_i$$$. Here is the reason
- Finally, here is 1D Dynamic Programming Solution
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
VI. Other solutions
Are there other approach for bigger N, C, V ?
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
VII. Tracing for selected elements
Which next state will lead to the best result ?
A) Solution for small number of element — N
- A) Permutation Approach: We will update selected elements when we see a better solution
- B) Bitmasking Approach: We will update bitmask when we see a better solution
- C) Meet-in-the-middle Approach: We will update bitmask when we see a better solution AND ON DP-CALCULATION.
B) Solution for small sum of weight — C[i]
- A) Recursive Dynamic Programming: Starting from $$$(i = 0, s = 0)$$$, we already have $$$magic(i,s)$$$ return the best result, $$$magic(i + 1,s + 0) + 0)$$$ or/and $$$magic(i + 1, s + c[i]) + v[i]$$$ will be the best result
- B) Iterative Dynamic Programming:
- C) Iterative Dynamic Programming (Space Optimization):
C) Solution for small sum of value — V[i]
- A) Recursive Dynamic Programming: Starting from $$$(i = 0, s = res)$$$, we already have $$$magic(i,s)$$$ return the best result, $$$magic(i + 1,s + 0) + 0)$$$ or/and $$$magic(i + 1, s - v[i]) + c[i]$$$ will be the best result
- B) Iterative Dynamic Programming:
- C) Iterative Dynamic Programming (Space Optimization):
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
VIII. Online Algorithm
How to solve the problem when you need to output the result whenever you receive new item ?
A) Solution for small number of element — N
- On progress...
B) Solution for small sum of weight — C[i]
- A) Recursive Dynamic Programming:
- B) Iterative Dynamic Programming:
- C) Iterative Dynamic Programming (Space Optimization):
C) Solution for small sum of value — V[i]
- A) Recursive Dynamic Programming:
- B) Iterative Dynamic Programming:
- C) Iterative Dynamic Programming (Space Optimization):
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
IX. Optimizations and Heuristic
How to improve the algorithm faster, shorter, simpler, safetier or saving space
A) Filtering the array
- 1) Split items into 2 types, whose weight less than $$$W$$$ and the rest
- 2) Compressed the array
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
X. Debugging
Support you when you are in a trouble that you cant find your bug
A) Wrong answer
1) Becareful when weight sum and value sum is big, it would cause overflow
2) Becareful that in Meet-in-the-middle approach:
You have to update the bitmask that have maxvalue.
You have to update the $$$maxval$$$ and $$$maxmask$$$ before assign $$$x.maxval$$$, $$$x.maxmask$$$
You have to use also in collecting the result
- 3) Forget base cases: In type $$$IV$$$ the DP is already init as 0, so you dont need the loop to zero, while the $$$V$$$ is not like that when you init it as $$$+oo$$$
B) Time Limit Exceed
1) Global variable $$$\neq$$$ Local variable
- In Meet-in-the-middle approach, the
solve()function didnt use global variable (n), it use $$$n = |c| = |s|$$$.
2) Forget to use memorization
3) You might get WA if you have wrong initalization or leave the value generated randomly
4) If you wanna binary search for the result, remember that you cant do Prefixmin DP $$$O(N \times SUM)$$$ as what it like in Prefixmax DP $$$O(N \times W)$$$
C) Memory limit exceed
1) Though Meet-in-the-middle approach is faster than Bitmasking Approach, it requires large amount of space — $$$O(2^{^{\frac{n}{2}}}$$$, which may give you MLE !
2) In some cases you will need space optimization if the limit is too tight !
3) Becareful in tracing results
D) Runtime Error
1) Out of bound
2) Array too big in main function: Declare it globally with the init size bigger than problem constraint a bit
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
X. Knapsack Variation and Practice Problems
In case you need a place to practice or submitting
- 2) Easy but nice problem — (contributor TheScrasse)
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |
XII. Blog status
The current progress and contributor of this blogs
Current progress;
- **1)** Online Algorithms - **2)** Remain space optimization while tracing for elements - **3)** Other solutions
On progress:
- **0)** Table of content & Complexity comparision table - **1)** Online Algorithm - **2)** Optimizations and Heuristic - **3a)** Unbounded knapsack - **3b)** Bounded knapsack - **3c)** Item limitation knapsack - **4a)** Knapsack query maximum value with item in range $$$[L, R]$$$ - **4b)** Knapsack query maximum value with weight in range $$$[L, R]$$$ - **4c)** Knapsack query minimum weight with value in range $$$[L, R]$$$ - **5a)** Multiple knapsack bags - **5b)** Multidimentional item
Special thank to contributors: SPyofgame, TheScrasse, Lusterdawn, jiangly
