Knapsack the tutorial

Revision en1, by SPyofgame, 2021-03-13 20:47:49


Teleporter: [Previous] | | | [Next]

Table of content

This blog isnt the best but worth spending time to read it

Teleporter Description
I. STATEMENT Taking about the problem
II. EXAMPLE To understand the problem better
III. Solution for small number of element — N How much will you get in each possible subset ?
IV. Solution for small sum of weight — C[i] What is the maximum value possible when your bag is exact $$$W$$$ weight ?
V. Solution for small sum of value — V[i] What is the minimum bag weight possible when it is exact $$$S$$$ sum value ?
VI. Tracing for selected elements Which next state will lead to the best result ?
VII. Other solutions How to solve the problem with special condition ?
VIII. Online Algorithm How to solve the problem when you need to output the result whenever you receive a new item ?
IX. Optimizations and Heuristic How to improve the algorithm faster, shorter, simpler, safetier or saving space
X. Debugging Support you when you are in a trouble that you cant find your bug
XI. Knapsack Variation and Practice Problems In case you need a place to practice or submitting
XII. Blog status The current progress and contributor of this blogs




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

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.





















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

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




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

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$$$


Permutation Approach - O(n!) time - O(n) space


B. Bitmasking Approach (Good) — $$$O(2^n \times 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$$$

Bitmasking Approach - O(2^n * n) time - O(n) space


C. Meet-in-the-middle Approach (Better) — $$$O(2^{^{\frac{n}{2}}} \times \frac{n}{2})$$$ time — $$$O(2^{^{\frac{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

Meet in the middle approach - O(2^(n/2) * (n/2)) time - O(2^(n/2)) space




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

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

Recursive Approach - O(NW) time - O(NW) space


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

Bad Approach - O(N^2 * W^2) time
Iterative Approach - O(NW) time - O(NW) space
Prefixmax DP Approach - O(NW) time - O(NW) space


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)$$$

Space Optimization Approach - O(NW) time - O(N + 2W) space


B) O(W) 1D — DP space

  • From the above algorithm, we can change the inner loop
Inner Part
  • 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.
Inner Part
  • Notice that it is required for the second-inner-loop to iterate from $$$w$$$ downto $$$c_i$$$. Here is the reason
From c[i] upto w
From w downto c[i]
  • Finally, here is 1D Dynamic Programming Solution
Space Optimization Approach - O(NW) time - O(N + 1W) space




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

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$$$

Recursive Approach - O(NSUM) time - O(NSUM) space


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$$$

Iterative Approach - O(NSUM) time - O(NSUM) space


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)$$$

Space Optimization Approach - O(NSUM) time - O(N + 2SUM) space


B) O(SUM) 1D — DP space

  • From the above algorithm, we can change the inner loop
Inner Part
  • 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.
Inner Part
  • Notice that it is required for the second-inner-loop to iterate from $$$sum$$$ downto $$$v_i$$$. Here is the reason
From v[i] upto sum
From sum downto v[i]
  • Finally, here is 1D Dynamic Programming Solution
Space Optimization Approach - O(NSUM) time - O(N + SUM) space




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

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
Permutation - O(n!) time - O(n) space

  • B) Bitmasking Approach: We will update bitmask when we see a better solution
O(2^n) time - O(n) space

  • C) Meet-in-the-middle Approach: We will update bitmask when we see a better solution AND ON DP-CALCULATION.
Bitmasking - O(2^(n/2) * (n/2)) time - O(2^(n/2)) space


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
Trace cases
Recursive DP - O(NW) time - O(NW) space

  • B) Iterative Dynamic Programming:
Prefixmax Iterative DP - O(NW) time - O(NW) space

  • C) Iterative Dynamic Programming (Space Optimization):
Explanation
Code


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
Trace cases
Recursive DP - O(NSUM) time - O(NSUM) space

  • B) Iterative Dynamic Programming:
Iterative DP - O(NSUM) time - O(NSUM) space

  • C) Iterative Dynamic Programming (Space Optimization):
Explanation
Code




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

VII. Other solutions

How to solve the problem with special condition ?



A) Fractional Knapsack & Greedy Approach

  • On progress...




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

VIII. Online Algorithm

How to solve the problem when you need to output the result whenever you receive a new item ?



A) Solution for small number of element — N

  • A) Permutation Approach: Really not worth being used thought it is possible to optimize it

  • B) Bitmasking Approach:
Explanation
Bitmasking Approach - O(2^N * N) time - O(n) space
DP Bitmask Approach - O(2^N) time - O(2^N) space

  • C) Iterating Deque Approach:
Explanation
Deque approach with little optimization - O(min(W, 2^N)) time - O(2^N) space
Deque approach with bad optimization - O(min(W, 2^N * N)) time - O(2^N * N) space

  • D) Recursive Approach:
Explanation
Recursive Approach - O(min(W, 2^N)) time - O(N) space
Recursive Approach with optimization - O(min(W, 2^N / 2^K)) time - O(N) space

  • E) Meet in the middle approach: On the progress...


B) Solution for small sum of weight — C[i]

  • A) Recursive Dynamic Programming:
What have changed from the orginal ?
O(NW) time - O(NW) space

  • B) Iterative Dynamic Programming:
What have changed from the orginal ?
O(NW) time - O(NW) space

  • C) Iterative Dynamic Programming (Space Optimization):
What have changed from the orginal ?
O(NW) time - O(W) space


C) Solution for small sum of value — V[i]

  • A) Recursive Dynamic Programming:
What have changed from the orginal ?
O(NSUM) time - O(NSUM) space

  • B) Iterative Dynamic Programming:
What have changed from the orginal ?
O(NSUM) time - O(NSUM) space

  • C) Iterative Dynamic Programming (Space Optimization):
What have changed from the orginal ?
O(NSUM) time - O(NSUM) space




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

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
Hint

  • 2) Compressed the array
Hint




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

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

Debug

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

Wrong
Wrong
Wrong
Debug
Debug

  • 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$$$
Wrong


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|$$$.
Debug

2) Forget to use memorization

Wrong
Wrong

3) You might get WA if you have wrong initalization or leave the value generated randomly

Wrong

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)$$$

Wrong


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

Wrong
Fixed


D) Runtime Error

1) Out of bound

Wrong
Wrong

2) Array too big in main function: Declare it globally with the init size bigger than problem constraint a bit





















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

XI. Knapsack Variation and Practice Problems

In case you need a place to practice or submitting



Hint

Note

Hint




Hint

Hint




Hint

Hint

Hint




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

XII. Blog status

The current progress and contributor of this blogs



  • Current progress;

    • 1) Online Algorithms
    • 2) Remain space optimization while tracing for elements
  • 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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SPyofgame 2021-03-13 20:47:49 106868 Initial revision (published)