Knapsack the tutorial

Revision en1, by SPyofgame, 2021-03-07 04:39:55

Teleporter: [Previous] | | | [Next]

Table of content

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. 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 ?
VIII. Online Algorithm How to solve the problem when you need to output the result whenever you receive 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$$$

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

Code
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

Code
――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

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

Code
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 transistion code - O(N^2 * W^2) time
Normal DP
Prefixmax DP
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)$$$

Code

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
Code
――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

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

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

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

Code

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
Code
――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

VI. Other solutions

Are there other approach for bigger N, C, V ?

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

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)) 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): On progress...
――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

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:
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]

X. Knapsack Variation and Practice Problems

In case you need a place to practice or submitting

Hint
Note
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

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

Tags knapsack, bruteforce, bitmasking, dp, 1d-dp, 2d-dp, tutorial, practice, meet-in-the-middle, knapsack 0/1, debugging, solutions

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English SPyofgame 2021-03-07 18:51:56 6 Tiny change: '\n```cpp\n mems' -> '\n```cpp\n\n mems'
en7 English SPyofgame 2021-03-07 18:57:04 3 Tiny change: '021-03-06]' -> '021-03-06]\n\n\n\n<spoiler summary="">\n\n```cpp\n</spoiler>'
en6 English SPyofgame 2021-03-07 18:54:30 5 Tiny change: '}\n }\n</spoile' -> '}\n }\n```\n</spoile'
en5 English SPyofgame 2021-03-07 18:48:18 92157
en4 English SPyofgame 2021-03-07 18:47:56 91522 Tiny change: '' -> '.'
en3 English SPyofgame 2021-03-07 05:31:28 48 Tiny change: 'rong> \n\n```\n\n<spoil' -> 'rong> \n\n~~~\n~~~\n\n<spoil'
en2 English SPyofgame 2021-03-07 05:28:42 3010
en1 English SPyofgame 2021-03-07 04:39:55 88488 Initial revision (published)