SC2001 Project 03

Dynamic Programming

Team 5

Part I

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} \]

Part II

Here's the subproblem graph, where each node represents the capacity and the edges represent the transitions between DP states.

Part III

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!

Part IV

Given w = [4, 6, 8] and p = [7, 6, 9], we obtained the following results.

The solution is dp[c] = 21 (c = 14).

Given w = [5, 6, 8] and p = [7, 6, 9], we obtained the following results.

The solution is dp[c] = 16 (c = 14).

An Alternative Solution

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.

What's the best way to compute $2^{64}$?

What's the best way to compute $2^{64}$?

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!

What about $2^{57}$?

What about $2^{57}$?

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.

What about $2^{57}$?

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

Thank You

https://github.com/anAcc22/SC2001_Group_Project

References

• Fenwick tree. Fenwick Tree - Algorithms for Competitive Programming. (2024, July 31). https://cp-algorithms.com/data_structures/fenwick.html
• USP, M. (2016). Problem L. The Knapsack Problem. Codeforces. https://codeforces.com/gym/101064/problem/L
• errorgorn. (2021). [tutorial] knapsack, subset sum and the (max,+) convolution. Codeforces. https://codeforces.com/blog/entry/98663