Dynamic Programming
Team 5
Because there are unlimited supplies of each type of object, this is referred to as the unbounded knapsack problem. Adopting the notation in the handout, our recursive definition is as follows.
\[ P(C) = \begin{cases} 0 & \text{if $C = 0$} \\ \max \left( \left\{ P(C-w_i) + p_i \right\} \right) & \text{for all $0 \leq i \leq n-1$ and $C \geq w_i$} \end{cases} \]
Here's the subproblem graph, where each node represents the capacity and the edges represent the transitions between DP states.
A natural way to perform bottom-up DP is to iterate over the objects and attempt to use each one to increase the profit at each capacity level.
A natural way to perform bottom-up DP is to iterate over the objects and attempt to use each one to increase the profit at each capacity level.
A natural way to perform bottom-up DP is to iterate over the objects and attempt to use each one to increase the profit at each capacity level.
It is evident that both the time and space complexity are $\mathcal{O}(nC)$.
Here's a revised implementation using $\mathcal{O}(C)$ memory.
Here's a revised implementation using $\mathcal{O}(C)$ memory.
For problems where there are multiple objects with the same weight, you could "fuse" them into one object with the best profit!
Given w = [4, 6, 8] and p = [7, 6, 9], we obtained the following results.
C | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
DP | 0 | 0 | 0 | 0 | 7 | 7 | 7 | 7 | 14 | 14 | 14 | 14 | 21 | 21 | 21 |
The solution is dp[c] = 21 (c = 14).
Given w = [5, 6, 8] and p = [7, 6, 9], we obtained the following results.
C | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
DP | 0 | 0 | 0 | 0 | 0 | 7 | 7 | 7 | 9 | 9 | 14 | 14 | 14 | 16 | 16 |
The solution is dp[c] = 16 (c = 14).
More often than not, you'll encounter situations where $n,C \leq 10^3$, so the $\mathcal{O}(nC)$ solution would pass comfortably.
More often than not, you'll encounter situations where $n,C \leq 10^3$, so the $\mathcal{O}(nC)$ solution would pass comfortably.
However, there are rare situations where you're given $w \leq 10^3, C \leq 10^9$. Let $W = w_{\max}$ from now on.
Let $a_i$ represent the answer to a given capacity $i$, observe that $a_i = \max_{j+k=i}(a_j + a_k)$, and we can further constraint $j$ and $k$ to $\lvert j - k \rvert \leq W$.
Let $a_i$ represent the answer to a given capacity $i$, observe that $a_i = \max_{j+k=i}(a_j + a_k)$, and we can further constraint $j$ and $k$ to $\lvert j - k \rvert \leq W$.
Suppose $j > k+W$, observe that we can repeatedly deduct $W$ from $j$ and add it to $k$, until the aforementioned property is satisfied; this can be thought of as moving the "slot" for a single object from $j$ to $k$.
If we had arrays $A$ and $B$ of length $n$ and $m$ respectively, the array $C$ of length $n+m-1$ constructed using $C_i = \max_{j+k=i}(A_j + B_k)$ is known as the $(\max, +)$ convolution.
If we had arrays $A$ and $B$ of length $n$ and $m$ respectively, the array $C$ of length $n+m-1$ constructed using $C_i = \max_{j+k=i}(A_j + B_k)$ is known as the $(\max, +)$ convolution.
Suppose we had $[a_{x-W},\ldots,a_{x},\ldots,a_{x+W}]$ and $[a_{y-W},\ldots,a_{y},\ldots,a_{y+W}]$, our goal is to compute $[a_{x+y-W},\ldots,a_{x+y},\ldots,a_{x+y+W}]$.
Convoluting $[a_{x-W},\ldots,a_{x},\ldots,a_{x+W}]$ with $[a_{y-W},\ldots,a_{y},\ldots,a_{y+W}]$ produces $[c_{x+y-2W},\ldots,c_{x+y},\ldots,c_{x+y+2W}]$, of which only $[c_{x+y-W},\ldots,c_{x+y}] = [a_{x+y-W},\ldots,a_{x+y}]$ is usable.
Convoluting this newly obtained $[a_{x+y-W},\ldots,a_{x+y}]$ with $[a_{0},\ldots,a_{W},\ldots,a_{2W}]$ yields $[c_{x+y-W},\ldots,c_{x+y+2W}]$ and $[c_{x+y+1},\ldots,c_{x+y+W}] = [a_{x+y+1},\ldots,a_{x+y+W}]$ may be used to obtain the "tail" of our desired array.
Convoluting this newly obtained $[a_{x+y-W},\ldots,a_{x+y}]$ with $[a_{0},\ldots,a_{W},\ldots,a_{2W}]$ yields $[c_{x+y-W},\ldots,c_{x+y+2W}]$ and $[c_{x+y+1},\ldots,c_{x+y+W}] = [a_{x+y+1},\ldots,a_{x+y+W}]$ may be used to obtain the "tail" of our desired array.
Concatenating $[a_{x+y-W},\ldots,a_{x+y}]$ with $[a_{x+y+1},\ldots,a_{x+y+W}]$ gives us $[a_{x+y-W},\ldots,a_{x+y},\ldots,a_{x+y+W}]$, as desired.
We could do it in $64$ steps, but what if we computed $2^{1}$, then used it to compute $2^{2}$, then $2^{4}$, followed by $2^{8}$ and so on?
This takes just seven steps!
Observe that in binary, $57$ is $111001$, so we could use $2^{(2^0)} \cdot 2^{(2^3)} \cdot 2^{(2^4)} \cdot 2^{(2^5)}$. These are precisely the values we've precomputed earlier.
Observe that in binary, $57$ is $111001$, so we could use $2^{(2^0)} \cdot 2^{(2^3)} \cdot 2^{(2^4)} \cdot 2^{(2^5)}$. These are precisely the values we've precomputed earlier.
In general, this principle is known as doubling, and it's used in data structures like Sparse Table and Fenwick Tree.
Let $b_i = [2^i \cdot W - W, \ldots, 2^i \cdot W , \ldots, 2^i \cdot W + W ]$, e.g., $b_0 = [0, \ldots, W , \ldots, 2W ]$.
A convolution may be implemented in $O(W^2)$ as described earlier.
"Merging" $[a_{x-W},\ldots,a_{x},\ldots,a_{x+W}]$ with $[a_{y-W},\ldots,a_{y},\ldots,a_{y+W}]$ to compute $[a_{x+y-W},\ldots,a_{x+y},\ldots,a_{x+y+W}]$ is a little tricky.
We may now build `lvls` from the bottom up.
Solving for a particular capacity can now be done.
Solving for a particular capacity can now be done.
Ultimately, this takes $O(W^2 \cdot \log(C))$ time and space complexity.
We now have the tools to solve this problem...
https://github.com/anAcc22/SC2001_Group_Project