en/docs/chapter_dynamic_programming/unbounded_knapsack_problem.md
In this section, we first solve another common knapsack problem: the unbounded knapsack, and then explore a special case of it: the coin change problem.
!!! question
Given $n$ items, where the weight of the $i$-th item is $wgt[i-1]$ and its value is $val[i-1]$, and a knapsack with capacity $cap$. **Each item can be selected multiple times**. What is the maximum value that can be placed in the knapsack within the capacity limit? An example is shown in the figure below.
The unbounded knapsack problem is very similar to the 0-1 knapsack problem, differing only in that there is no limit on the number of times an item can be selected.
Under the rules of the unbounded knapsack problem, the changes in state $[i, c]$ are divided into two cases.
Thus, the state transition equation becomes:
$$ dp[i, c] = \max(dp[i-1, c], dp[i, c - wgt[i-1]] + val[i-1]) $$
Comparing the code for the two problems, there is one change in state transition from $i-1$ to $i$, with everything else identical:
[file]{unbounded_knapsack}-[class]{}-[func]{unbounded_knapsack_dp}
Since the current state is transferred from states on the left and above, after space optimization, each row in the $dp$ table should be traversed in forward order.
This traversal order is exactly opposite to the 0-1 knapsack. Please refer to the figure below to understand the difference between the two.
=== "<1>"
=== "<2>"
=== "<3>"
=== "<4>"
=== "<5>"
=== "<6>"
The code implementation is relatively simple, just delete the first dimension of the array dp:
[file]{unbounded_knapsack}-[class]{}-[func]{unbounded_knapsack_dp_comp}
The knapsack problem represents a large class of dynamic programming problems and has many variants, such as the coin change problem.
!!! question
Given $n$ types of coins, where the denomination of the $i$-th type of coin is $coins[i - 1]$, and the target amount is $amt$. **Each type of coin can be selected multiple times**. What is the minimum number of coins needed to make up the target amount? If it is impossible to make up the target amount, return $-1$. An example is shown in the figure below.
The coin change problem can be viewed as a special case of the unbounded knapsack problem, with the following connections and differences.
Step 1: Think about the decisions in each round, define the state, and thus obtain the $dp$ table
State $[i, a]$ corresponds to the subproblem: the minimum number of coins among the first $i$ types of coins that can make up amount $a$, denoted as $dp[i, a]$.
The two-dimensional $dp$ table has size $(n+1) \times (amt+1)$.
Step 2: Identify the optimal substructure, and then derive the state transition equation
This problem differs from the unbounded knapsack problem in the following two aspects regarding the state transition equation.
$$ dp[i, a] = \min(dp[i-1, a], dp[i, a - coins[i-1]] + 1) $$
Step 3: Determine boundary conditions and state transition order
When the target amount is $0$, the minimum number of coins needed to make it up is $0$, so all $dp[i, 0]$ in the first column equal $0$.
When there are no coins, it is impossible to make up any amount $> 0$, which is an invalid solution. To enable the $\min()$ function in the state transition equation to identify and filter out invalid solutions, we consider using $+ \infty$ to represent them, i.e., set all $dp[0, a]$ in the first row to $+ \infty$.
Most programming languages do not provide a $+ \infty$ variable, and can only use the maximum value of integer type int as a substitute. However, this can lead to large number overflow: the $+ 1$ operation in the state transition equation may cause overflow.
For this reason, we use the number $amt + 1$ to represent invalid solutions, because the maximum number of coins needed to make up $amt$ is at most $amt$. Before returning, check whether $dp[n, amt]$ equals $amt + 1$; if so, return $-1$, indicating that the target amount cannot be made up. The code is as follows:
[file]{coin_change}-[class]{}-[func]{coin_change_dp}
The figure below shows the dynamic programming process for coin change, which is very similar to the unbounded knapsack problem.
=== "<1>"
=== "<2>"
=== "<3>"
=== "<4>"
=== "<5>"
=== "<6>"
=== "<7>"
=== "<8>"
=== "<9>"
=== "<10>"
=== "<11>"
=== "<12>"
=== "<13>"
=== "<14>"
=== "<15>"
The space optimization for the coin change problem is handled in the same way as the unbounded knapsack problem:
[file]{coin_change}-[class]{}-[func]{coin_change_dp_comp}
!!! question
Given $n$ types of coins, where the denomination of the $i$-th type of coin is $coins[i - 1]$, and the target amount is $amt$. Each type of coin can be selected multiple times. **What is the number of coin combinations that can make up the target amount?** An example is shown in the figure below.
Compared to the previous problem, this problem's goal is to find the number of combinations, so the subproblem becomes: the number of combinations among the first $i$ types of coins that can make up amount $a$. The $dp$ table remains a two-dimensional matrix of size $(n+1) \times (amt + 1)$.
The number of combinations for the current state equals the sum of the combinations from not selecting the current coin and selecting the current coin. The state transition equation is:
$$ dp[i, a] = dp[i-1, a] + dp[i, a - coins[i-1]] $$
When the target amount is $0$, no coins need to be selected to make up the target amount, so all $dp[i, 0]$ in the first column should be initialized to $1$. When there are no coins, it is impossible to make up any amount $>0$, so all $dp[0, a]$ in the first row equal $0$.
[file]{coin_change_ii}-[class]{}-[func]{coin_change_ii_dp}
The space optimization is handled in the same way, just delete the coin dimension:
[file]{coin_change_ii}-[class]{}-[func]{coin_change_ii_dp_comp}