Dynamic programming (DP) solves a problem by combining the optimal values of subproblems stored in a table. Which two properties must the problem have for DP to be correct and useful?
Optimal substructure and overlapping subproblems
Optimal substructure and independent subproblems
Linear objective function and integer constraints
Totally unimodular matrix and integer data
Explanation. Optimal substructure makes the recurrence correct; overlapping subproblems make the lookup table, which stores the values already computed, useful.
A dynamic programming (DP) algorithm fills a table with the optimal values of the subproblems. How is an optimal solution obtained, besides the optimal value?
Reading only the table of values forward, from the initial to the final state
Re-running the recursion top-down, without any memorization
Storing the decisions in another table and reading them backward from the final state
Storing the decisions in another table and reading them forward from the initial state
Explanation. The design has two steps: the optimal value (recurrence, base cases, bottom-up table) and an optimal solution (decisions stored and read backwards).
A dynamic programming (DP) algorithm follows the «divide, conquer and combine» paradigm. What does the combining principle say?
The best subproblem is chosen and the others are discarded
An optimal solution of the problem is built from optimal solutions of the subproblems
The problem is decomposed into smaller subproblems of the same type
Small subproblems are solved directly, without recursion
Explanation. Dividing generates the subproblems, conquering solves them (recursively, or directly if small), combining merges their optimal solutions into an optimal solution of the problem.
For the knapsack problem with $n$ items brute force lists the $2^n$ subsets. How does dynamic programming (DP) avoid this enumeration?
It stores the optimal value of every subproblem in a table and reuses it when the subproblem appears again
It discards a priori the subsets with low profit, as a greedy heuristic
It solves the LP relaxation and rounds the solution
It examines the subsets in random order and stops at the first feasible one
Explanation. The distinct subproblems are far fewer than the solutions (for the KP $(n+1)(c+1)$ against $2^n$): each is solved once and its value is read from the table (lookup table).
In dynamic programming (DP) the subproblems generated by the decomposition are «independent». What does this mean?
Each appears only once in the recursion
They all have the same size
Their optimal solutions have no element in common
Each can be solved without information on the solution of the others
Explanation. Independent means that a subproblem is solved on its own; it may however appear several times in the recursion (overlapping subproblems), and this is exactly what makes the table useful.
In dynamic programming (DP), what does the optimal substructure property of a recursive decomposition state?
Every optimal solution of a subproblem is also optimal for the problem
The subproblems repeat many times in the recursion
An optimal solution of the problem is obtained by combining optimal solutions of its subproblems
Every subproblem has a unique optimal solution
Explanation. Optimal substructure guarantees the correctness of the recurrence; the repetition of subproblems is the other property, overlapping subproblems, which makes DP efficient.
What is the first step in the design of a dynamic programming (DP) algorithm?
Compute an upper bound with a heuristic
Identify the recursive decomposition into subproblems and check optimal substructure and overlapping subproblems
Write the integer linear programming model and its relaxation
Sort the data by non-increasing efficiency
Explanation. First the decomposition is defined and the two properties are checked; then the optimal value is computed with the recurrence and the base cases, and finally an optimal solution is rebuilt.
In dynamic programming (DP) the optimal value can be computed top-down (recursion with a table) or bottom-up. What does the bottom-up approach require?
An order of the subproblems in which each comes after those it depends on
That the subproblems never repeat
That the table is filled in random order
That the recurrence has a single base case
Explanation. Bottom-up fills the table from the base cases, in an order (for example increasing capacities) that makes the cells read by the recurrence already available. Top-down follows the recursion instead and stores the computed values.
Among the dynamic programming algorithms of the module, which one has a number of steps polynomial in the input size (and not only pseudo-polynomial)?
The DP for the 0-1 knapsack, $\Theta(nc)$
The DP for the bounded knapsack, $\Theta(nc\,b_{\max})$
The DP for capacitated lot sizing, $O(mDC)$
Wagner and Whitin for uncapacitated lot sizing, $\Theta(m^2)$ with $m$ periods
Explanation. $m$ is the number of periods, and the input contains $m$ demands: $\Theta(m^2)$ is polynomial. The other times contain numbers of the input (capacity $c$, bound $b_{\max}$, demand $D$), exponential in the number of digits.
In dynamic programming for the multidimensional knapsack (MDKP) and the multiple knapsack (MKP), the state contains a vector of $m$ residual capacities. When is the number of steps pseudo-polynomial?
Never, since the vector makes the problem strongly polynomial
Only when all the capacities are equal
Only for a fixed number $m$ of dimensions or knapsacks
Always, since every capacity is a number of the input
Explanation. The table has one dimension per capacity, hence $\prod_d(c_d+1)$ states: with fixed $m$ it is pseudo-polynomial, with $m$ part of the input it grows exponentially in $m$.
In a dynamic programming (DP) algorithm, what does the lookup table contain?
The subproblems still to be solved, in priority order
The optimal value of every subproblem already solved, read when the subproblem appears again
The list of all feasible solutions of the problem
The LP relaxation solutions of every subproblem
Explanation. The table avoids recomputing overlapping subproblems: every value is computed once. To rebuild a solution the decisions are also stored, in another table.
Dynamic programming requires optimal substructure: an optimal solution is composed of optimal solutions of the subproblems. What happens in a problem where this property is missing?
The DP becomes polynomial
The table has fewer cells
Combining the optimal values of the subproblems may give a non-optimal solution, and the recursion is not correct
The DP stays correct but slower
Explanation. Without optimal substructure the optimal solution may use, for a subproblem, a non-optimal solution, which the table does not store.
Among the DP algorithms of the module, which pair has a number of steps exponential in the number of capacity constraints (knapsacks or dimensions), and not only pseudo-polynomial?
Uncapacitated lot sizing and knapsack with setups
Multidimensional knapsack and multiple knapsack, with one state for every capacity vector
0/1 knapsack and subset sum
Rod cutting and coin change
Explanation. The state is a vector $\vet k$ with $\prod(c_d+1)$ values: exponential in the number of capacities. The other algorithms have a single capacity or are polynomial.
A recursive algorithm without memory and a dynamic programming algorithm use the same recursion. Why can the DP take pseudo-polynomial instead of exponential time?
The subproblems repeat, and the DP solves each one only once storing its value in the table
Because the DP examines fewer feasible solutions per subproblem
Because the DP uses a different recursion
Because the DP does not need optimal substructure
Explanation. The number of distinct subproblems (e.g., $(n+1)(c+1)$ for the knapsack) bounds the work; recursion without memory recomputes them every time they appear.
Dynamic programming algorithms require two properties of the problem: optimal substructure and overlapping subproblems. What happens if the subproblems do not overlap (each appears only once)?
The DP becomes incorrect
The DP becomes polynomial
The table has more cells than subproblems
The DP stays correct but saves nothing compared to recursion: a «divide and conquer» approach is preferable
Explanation. Memoization only helps if a subproblem is requested several times; without overlap the cost is the same as recursion.
In the design of a dynamic programming algorithm, after defining the subproblems and the recursive formula with the base cases, in which order is the table filled in the bottom-up approach?
From the largest subproblem to the smallest
Only along the diagonal
In an order where every subproblem comes after all those it depends on
In random order
Explanation. In the knapsack DP, for instance, row $j$ uses only row $j-1$: the rows are filled in increasing order. Then the solution is reconstructed going back through the table.
Among the dynamic programming algorithms of the module, which have a number of steps polynomial in the instance size, and not only pseudo-polynomial?
All of them
Wagner-Whitin for uncapacitated lot sizing ($\Theta(m^2)$) and rod cutting ($\Theta(n^2)$)
The DP of the 0/1 knapsack and that of the subset sum
The DP of the multidimensional knapsack
Explanation. In the ULS the number of steps depends only on the number of periods; in rod cutting $n$ is also the number of prices in input. The knapsack DPs depend on the value of the capacity.
A problem has optimal substructure and overlapping subproblems. What does a dynamic programming (DP) algorithm based on a correct recurrence guarantee?
An optimal solution in time polynomial in the input
A solution with a guaranteed approximation ratio
Each subproblem solved as many times as it appears
An optimal solution, with each subproblem solved only once
Explanation. Optimal substructure makes the recurrence exact; the table avoids recomputing the subproblems. The running time may be only pseudo-polynomial.
In dynamic programming (DP), which property of the problem makes the recurrence correct, that is, makes it give the optimal value?
Integer positive data
A polynomial number of subproblems
Optimal substructure
Overlapping subproblems
Explanation. With optimal substructure an optimal solution is made of optimal solutions of subproblems. Overlapping subproblems make the table useful, not the recurrence correct.
A DP algorithm has $S$ distinct subproblems and computes each one by comparing at most $d$ known values, each in constant time. How many steps does it execute to fill the table?
$O(S+d)$
$O(S^{d})$
$O(d^{S})$
$O(S\,d)$
Explanation. Each subproblem is computed once, with $O(d)$ steps: $O(S\,d)$ in total.
In dynamic programming for the knapsack problem (KP: weights $w_j$, capacity $c$), with a single vector $v[0..c]$ updated item by item, why are the capacities $k$ scanned from $c$ down to $0$ for every item $j$?
Otherwise $v[k-w_j]$ would not be computed yet, and the recurrence would read empty cells
This way the number of steps drops from $\Theta(nc)$ to $\Theta(c)$, since half the vector is skipped
This way the cell $v[c]$, which contains the optimal value, is filled first
Otherwise $v[k-w_j]$ would already contain item $j$, which could be chosen several times
Explanation. Scanning in increasing order would read a value already updated with item $j$, and would solve the unbounded knapsack. The number of steps remains $\Theta(nc)$.
In the knapsack problem (KP, capacity $c$, $P=\sum_j p_j$), the second DP algorithm computes $u(j,q)$, the minimum weight of a subset of $\{1,\dots,j\}$ with total profit exactly $q$. Where is the optimal value read?
$\max\{u(n,q): q\in\{0,\dots,P\}\}$
$u(n,c)$
$\max\{q\in\{0,\dots,P\}: u(n,q)\le c\}$
$\min\{q\in\{0,\dots,P\}: u(n,q)\ge c\}$
Explanation. $u(n,q)$ is not a profit but a minimum weight: profit $q$ is attainable if the minimum weight does not exceed the capacity. This algorithm executes $\Theta(nP)$ steps.
In the DP for the knapsack problem, $v(j,k)$ is the optimal value with items $1,\dots,j$ and capacity $k$. In the reconstruction of an optimal solution, starting from $(n,c)$, how are the indices updated when item $j$ is chosen?
$j$ decreases by $1$ and $k$ decreases by $p_j$
$j$ decreases by $1$ and $k$ decreases by $w_j$
$j$ decreases by $1$ and $k$ stays the same
$j$ stays the same and $k$ decreases by $w_j$
Explanation. At every step the item index decreases by one; the capacity decreases by $w_j$ only if item $j$ is selected (i.e., if $v(j,k)\ne v(j-1,k)$).
In the first DP for the 0-1 knapsack (KP), $v(j,k)$ is the largest profit with items $1,\dots,j$ and capacity $k$, for $j=0,\dots,n$ and $k=0,\dots,c$. How many cells does the table have with $n=4$ items and capacity $c=9$?
$40$
$16$
$50$
$36$
Explanation. $(n+1)(c+1)=5\cdot 10=50$: rows start at $j=0$ and columns at $k=0$. $16=2^4$ counts the subsets of the items.
In the list-based DP for the 0-1 knapsack, a state is a pair (weight, profit) of a subset, and $L_j$ keeps the non-dominated states with items $1,\dots,j$; $(w,p)$ dominates $(w',p')$ if $w\le w'$ and $p\ge p'$. With items $(w_1,p_1)=(2,6)$, $(w_2,p_2)=(3,5)$ and $L_0=\{(0,0)\}$, how many states does $L_2$ have?
$5$
$3$
$4$
$2$
Explanation. The subsets give $(0,0)$, $(2,6)$, $(3,5)$, $(5,11)$; $(3,5)$ is dominated by $(2,6)$, which weighs less and is worth more. $3$ states remain.
In the list-based DP for the 0-1 knapsack (integer capacity $c$), the list $L_j$ contains only non-dominated (weight, profit) states of weight at most $c$. Why does it have at most $c+1$ states?
Non-dominated states have pairwise different weights, and the possible integer weights are $0,1,\dots,c$
Every item adds at most one state to the list
Non-dominated states all have the same profit
The list is emptied when it exceeds $c$ elements
Explanation. Two states with the same weight are comparable, and one dominates the other; hence in $L_j$ the weights are distinct and, sorted by increasing weight, the profits are increasing too. The number of states is therefore at most $\min\{2^j,c+1\}$.
In the list-based DP for the 0-1 knapsack, why can a state $(w',p')$ dominated by $(w,p)$, i.e., with $w\le w'$ and $p\ge p'$, be discarded?
Because $(w',p')$ is infeasible
Because dominated states always weigh more than the capacity
Because the list must have at most $n$ elements
Every set of remaining items that can be added to $(w',p')$ can be added to $(w,p)$ too, with no smaller profit
Explanation. If $S'$ fits with $(w',p')$, it fits with $(w,p)$ too since $w\le w'$, and gives profit $p+p(S')\ge p'+p(S')$: no optimal solution is lost.
In the second DP for the 0-1 knapsack, $u(j,q)$ is the minimum weight of a subset of items $1,\dots,j$ with profit exactly $q$, for $q=0,\dots,P$ with $P=\sum_j p_j$. How many cells does the table have with profits $p=(6,5,8,9)$?
$50$
$140$
$145$
$116$
Explanation. $P=28$, hence $(n+1)(P+1)=5\cdot 29=145$. The number of steps is $\Theta(nP)$: it pays off when the profits are small compared with the capacity.
In the second DP for the 0-1 knapsack, $u(j,q)$ is the minimum weight of a subset of items $1,\dots,j$ with profit exactly $q$ ($+\infty$ if none exists). Items: $p=(3,2,4)$, $w=(4,3,5)$. What is $u(3,5)$?
$8$
$7$
$+\infty$
$5$
Explanation. The only subset with profit $5$ is $\{1,2\}$, of weight $4+3=7$. $\{1,3\}$ has profit $7$, not $5$; $5$ mixes up weight and profit.
In the second DP for the 0-1 knapsack, $u(n,q)$ is the minimum weight to get profit exactly $q$. With capacity $c=8$ the last row, for $q=0,\dots,8$, is $(0,+\infty,3,4,+\infty,7,6,9,10)$. What is the optimal knapsack value?
$6$
$8$
$5$
$7$
Explanation. The optimal value is the largest $q$ with $u(n,q)\le c$: $u(n,8)=10$ and $u(n,7)=9$ exceed $8$, $u(n,6)=6\le 8$. Hence $6$.
In the list implementation of the second DP for the 0-1 knapsack ((weight, profit) states, lists $L_j$ of non-dominated states), when is the capacity $c$ used?
At every step: states heavier than $c$ are discarded at once
At the start: items heavier than $c/2$ are discarded
Never: the optimal value is the largest profit in $L_n$
Only at the end: among the states of $L_n$ those of weight at most $c$ are taken
Explanation. As in the recurrence on $u(j,q)$, the capacity does not appear in the lists: $L_j$ collects the states of all subsets, even too heavy ones, and the check $w\le c$ is done on $L_n$.
In the list-based DP for the 0-1 knapsack, the last list of non-dominated (weight, profit) states is $L_n=\{(0,0),(2,6),(5,11),(8,14),(9,15),(11,19)\}$ and the capacity is $c=9$. What is the optimal value?
$14$
$11$
$15$
$19$
Explanation. Among the states of weight at most $9$ the largest profit is $15$, of state $(9,15)$. $(11,19)$ exceeds the capacity.
0/1 knapsack with capacity $c=5$ and $3$ items, $p=(6,7,8)$ and $w=(2,3,3)$. Of the $8$ subsets of items, how many are feasible solutions (total weight at most $c$)?
$4$
$5$
$6$
$8$
Explanation. Only $\{2,3\}$ (weight $6$) and $\{1,2,3\}$ (weight $8$) are infeasible; the empty set, the three singletons, $\{1,2\}$ and $\{1,3\}$ (weight $5$) are feasible.
0/1 knapsack with capacity $c=5$, profits $p=(6,7,8)$ and weights $w=(2,3,3)$. What is the optimal value, found by enumerating the subsets?
$21$
$14$
$15$
$13$
Explanation. $\{1,3\}$ weighs $5$ and is worth $14$; $\{1,2\}$ is worth $13$; $\{2,3\}$ would be worth $15$ but weighs $6>5$; $21$ is the sum of all profits.
A solution of the 0/1 knapsack with $n$ items is encoded by the binary vector $(x_1,\dots,x_n)$. With $p=(6,7,8)$, $w=(2,3,3)$ and $c=5$, what does $(1,0,1)$ represent?
The solution $\{1,3\}$, of weight $5\le c$ and profit $14$
The solution $\{2\}$, of weight $3$ and profit $7$
An infeasible solution of weight $8$
Two copies of item $1$ and one of item $3$
Explanation. $x_j=1$ if and only if item $j$ is selected: weight $2+3=5$, profit $6+8=14$. Multiple copies belong to the unbounded knapsack.
The DP algorithm for the 0/1 knapsack performs $\Theta(nc)$ steps ($n$ items, capacity $c$). The capacity and all weights of an instance are multiplied by $1000$. What happens to the number of steps and to the instance size (in bits)?
Both grow $1000$ times
The steps do not change, since the optimal solution is the same
The steps grow about $10$ times
The steps grow about $1000$ times, the size only by about $10$ bits per number
Explanation. $\Theta(nc)$ depends on the value of $c$, while writing $1000c$ needs only $\log_2 1000\approx10$ more bits: this is why the algorithm is pseudo-polynomial and not polynomial.
The DP for the 0/1 knapsack has a version with the matrix $v(j,k)$, $(n+1)(c+1)$ cells, and a version with a single vector of $c+1$ cells. How do number of steps and memory compare?
The vector requires $\Theta(nc^2)$ steps
Identical also in memory
Same number of steps $\Theta(nc)$; the vector uses memory $\Theta(c)$ instead of $\Theta(nc)$
The vector is faster, $\Theta(c)$ steps
Explanation. Both run the same two nested loops; the vector reuses the same row for every item (scanning the capacities from $c$ down to $w_j$), but does not keep the table to reconstruct the solution.
In the list-based DP for the 0/1 knapsack, the list $L_j$ contains the non-dominated states built with items $1,\dots,j$, with distinct weights in $\{0,\dots,c\}$. With $c=100$, at most how many states can $L_3$ contain?
$300$
$8$, because $|L_j|\le\min\{2^j,c+1\}$
$101$
$3$
Explanation. With three items there are $2^3=8$ subsets, hence at most $8$ states, far fewer than the $101$ capacities of the matrix.
The second DP algorithm for the 0/1 knapsack computes, for every target profit $q\in\{0,\dots,P\}$ with $P=\sum_jp_j$, the minimum weight to obtain it, in $\Theta(nP)$ steps. When is it preferable to the first algorithm, $\Theta(nc)$?
When the profits are small and the capacity is large ($P\ll c$)
When the capacity is small and the profits large
Always, because $\Theta(nP)$ is polynomial
Never: the two algorithms always have the same number of steps
Explanation. The two algorithms are pseudo-polynomial in different numbers; the second one underlies the FPTAS, which rounds the profits to make $P$ small.
In the second DP for the 0/1 knapsack, the matrix $u(j,q)$ (minimum weight to obtain profit $q$ with items $1,\dots,j$) has $(n+1)(P+1)$ cells, with $P=\sum_jp_j$. Why can the list implementation be much smaller?
Because the lists ignore the heavy items
Because the lists store only the last row
It is not: they always have $(n+1)(P+1)$ elements
Most cells are $+\infty$ (unreachable profits); the lists keep only the reachable states
Explanation. With items $1,\dots,j$ at most $2^j$ different profits are obtained, hence $|L_j|\le\min\{2^j,P+1\}$; the $+\infty$ cells do not enter the lists.
0/1 knapsack with $n$ items: how many subsets of items are there, and how many of them does the DP consider explicitly?
$n!$ subsets; the DP considers $n^2$ of them
$n^2$ subsets; the DP considers all of them
$2^n$ subsets; the DP does not enumerate them, but computes $(n+1)(c+1)$ values $v(j,k)$
$2^n$ subsets; the DP considers all of them
Explanation. Every item is chosen independently, hence $2^n$. The DP groups the subsets by (last item considered, capacity used) and keeps only the best one.
Counting the lines of the pseudocode, the first DP for the 0/1 knapsack performs in the worst case $S(n,c)=4nc+4n+2c+4$ steps. How many are they for $n=3$ and $c=5$, and what is the order of growth?
$86$; $\Theta(n+c)$
$60$; $\Theta(nc)$
$96$; $\Theta(n^2c)$
$86$; $\Theta(nc)$
Explanation. $4\cdot15+12+10+4=86$. The dominant term is $4nc$, hence $S(n,c)=\Theta(nc)$: the limit of $S/(nc)$ is $4$.
In the list-based DP for the 0/1 knapsack, for every item $M_j$ is built from $L_{j-1}$ and the two lists are merged with Merge. Why do the steps remain $\Theta(nc)$ in the worst case?
Because Merge sorts the lists in $\Theta(c\log c)$
Because the lists ignore the capacity
Every list has at most $c+1$ states (distinct weights in $\{0,\dots,c\}$), and Merge scans them once per item
Because the lists always have a single state
Explanation. $|L_{j-1}|+|M_j|\le2(c+1)$ states per item, with constant work per state; on average the lists are much shorter than the matrix.
On the 0/1 knapsack instance with $c=5$, $p=(6,7,8)$, $w=(2,3,3)$ the DP lists contain $1$, $2$, $4$ and $4$ states. How many cells does the matrix $v(j,k)$ have instead?
$8$
$24$, i.e., $(n+1)(c+1)$
$11$
$15$
Explanation. $(3+1)(5+1)=24$ cells, against $11$ states overall in the lists: the lists store only reachable, non-dominated states.
The second DP for the 0/1 knapsack performs $S(n,P)=4nP+7n+4P+8$ steps, with $P=\sum_jp_j$. With $n=3$ and profits $p=(6,7,8)$, what is $S$?
$365$
$252$
$86$
$345$
Explanation. $P=21$: $4\cdot3\cdot21+7\cdot3+4\cdot21+8=252+21+84+8=365$. $252$ is only the dominant term; $86$ is the number of steps of the first DP with $c=5$.
The second DP for the 0/1 knapsack has a version with matrix $u(j,q)$ and one with a single vector indexed by the target profit $q\in\{0,\dots,P\}$. How much memory does the vector version use?
$\Theta(nP)$, as the matrix
$\Theta(c)$
$\Theta(n)$
$\Theta(P)$, with the same number of steps $\Theta(nP)$
Explanation. The vector has $P+1$ cells and is updated item by item; as for the first DP, giving up the matrix complicates the reconstruction of the solution.
In the second list-based DP for the 0/1 knapsack the states have distinct profits in $\{0,\dots,P\}$, with $P=\sum_jp_j$. With $P=21$, at most how many states can the list $L_2$, built with the first two items, contain?
$2$
$21$
$4$, because $|L_j|\le\min\{2^j,P+1\}$
$22$
Explanation. Two items give $2^2=4$ subsets, hence at most $4$ different profits, far fewer than the $P+1=22$ columns of the matrix.
The matrix $u(j,q)$ of the second DP for the 0/1 knapsack (minimum weight to obtain exactly profit $q$ with items $1,\dots,j$) has $(n+1)(P+1)$ cells. How many are they with $n=3$ and $p=(6,7,8)$?
$84$
$88$
$63$
$24$
Explanation. $P=21$, hence $4\cdot22=88$; most of them are $+\infty$, since few profits are reachable. $24$ are the cells of the first DP with $c=5$.
In the first list-based DP for the 0/1 knapsack $|M_j|\le|L_{j-1}|$, in the second (states indexed by profit) $|M_j|=|L_{j-1}|$. What does the difference depend on?
In the first, adding item $j$ to a state may exceed the capacity and the state is discarded; in the second every state is extended with item $j$
The second DP ignores the weights
In the second the lists are sorted by weight
There is no difference: equality holds in both
Explanation. In the second DP the minimum weight is compared with $c$ only at the end, to choose the largest reachable profit.
The second DP algorithm for the 0/1 knapsack computes $u(j,q)$, the minimum weight to obtain exactly the profit $q$. Which hypothesis on the data is needed?
An even capacity $c$
Pairwise distinct profits $p_j$
Integer profits $p_j$
Integer weights $w_j$
Explanation. The indices $q$ are the profits $0,1,\dots,P$: integer profits are needed; weights can be arbitrary.
For the 0/1 knapsack with capacity $c$ and total profit $P$ there are a DP in $\Theta(nc)$ and a DP by profits in $\Theta(nP)$. When is the second one better?
When $P<c$
When $c<P$
When all weights are $1$
Never
Explanation. The two times differ only by the factor $c$ or $P$: with small profits the DP by profits is better.
In the implementation with lists of the DP for the 0/1 knapsack a state (weight $W$, profit $Q$) dominated by $(W',Q')$ is discarded. When is there dominance?
$W'\ge W$ and $Q'\ge Q$
$W'+Q'\ge W+Q$
$W'\le W$ and $Q'\le Q$
$W'\le W$ and $Q'\ge Q$, with at least one strict inequality
Explanation. A state that weighs more and earns no more never leads to a better solution.
In the unbounded knapsack problem (UKP: $n$ item types, profit $p_j$, weight $w_j$, unlimited copies), the DP with table $v(j,k)$ (types $1,\dots,j$, capacity $k$) uses a recurrence with two terms. Which term allows using several copies of type $j$?
$p_j+v(j-1,k)$, which does not reduce the capacity
$v(j-1,k)$, which excludes type $j$
$p_j+v(j,k-w_j)$, which stays in row $j$
$p_j+v(j-1,k-w_j)$, which moves to row $j-1$
Explanation. Staying in row $j$ after inserting a copy allows inserting more; with row $j-1$ one would get the 0/1 KP.
In the unbounded knapsack problem (UKP), $v(k)$ is the maximum profit with capacity $k$ and unlimited copies of every type. What is $v(k)$ if no item type fits into capacity $k\ge 1$?
$v(k-1)$: the previous capacity is used
$0$: part of the capacity may stay unused
$-\infty$: the capacity must be filled exactly
$+\infty$: the subproblem is infeasible
Explanation. The capacity need not be filled: if no type fits, the empty solution is feasible and is worth $0$. The value $+\infty$ is used in coin change, where the amount must be returned exactly.
In the unbounded knapsack problem (UKP: $n$ item types, capacity $c$), the first DP algorithm fills a vector $v$ indexed by the residual capacity. How many cells does it have and how many steps does it execute?
$c+1$ cells, $\Theta(nc)$ steps
$c$ cells, $\Theta(c)$ steps
$(n+1)(c+1)$ cells, $\Theta(nc)$ steps
$c+1$ cells, $\Theta(n^2c)$ steps
Explanation. The optimal value depends only on the residual capacity, so a vector of $c+1$ cells (from $0$ to $c$) is enough; for each cell the $n$ types are tried: $\Theta(nc)$, pseudo-polynomial.
In the unbounded knapsack (UKP) type $j$ can be used at most $\lfloor c/w_j\rfloor$ times. With weights $w=(2,3,4)$ and capacity $c=8$, how many vectors $(x_1,x_2,x_3)$ with $0\le x_j\le\lfloor c/w_j\rfloor$ are there, before checking the capacity?
$27$
$8$
$60$
$45$
Explanation. $\lfloor 8/2\rfloor+1=5$, $\lfloor 8/3\rfloor+1=3$, $\lfloor 8/4\rfloor+1=3$: $5\cdot3\cdot3=45$ candidate vectors, of which only some respect the capacity.
Unbounded knapsack (UKP) with two types, $p=(3,5)$ and $w=(2,3)$, capacity $c=7$. With $v(0)=0$ and $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$ ($0$ if no type fits), what is $v(7)$?
$8$
$12$
$11$
$10$
Explanation. $v=(0,0,3,5,6,8,10,11)$ for $k=0,\dots,7$: for example two copies of type $1$ and one of type $2$. The greedy by efficiency (two copies of type $2$) gives $10$, the 0-1 knapsack gives $8$.
In the first DP for the unbounded knapsack (UKP), $v(k)$ is the largest profit with capacity $k$ and $s(k)$ the type attaining the maximum in the recurrence. How is an optimal solution rebuilt starting from $k=c$?
Read $s(c)$: all the copies are of that type
Take one copy of type $s(k)$ and set $k\leftarrow k-w_{s(k)}$, until no type fits
Take type $s(k)$ and move to the next type, as in the KP
Take $\lfloor k/w_{s(k)}\rfloor$ copies of $s(k)$ and stop
Explanation. Every step of the recurrence adds one copy of a type and reduces the capacity by its weight; the type may repeat in later steps.
In the second DP for the unbounded knapsack (UKP), $v(j,k)=\max\{v(j-1,k),\ p_j+v(j,k-w_j)\}$ (the second term if $w_j\le k$). In which order are the cells computed bottom-up?
Row by row (increasing $j$) and, in every row, by increasing $k$
Row by row and, in every row, by decreasing $k$
Column by column, by decreasing $j$
In any order, because the cells are independent
Explanation. $v(j,k)$ reads $v(j-1,k)$ (previous row) and $v(j,k-w_j)$ (same row, smaller capacity): the latter must already be computed, so $k$ increases. This is what allows several copies of type $j$.
Unbounded knapsack (UKP) with types $p=(3,5)$, $w=(2,3)$. In the second DP, $v(j,k)$ is the largest profit with types $1,\dots,j$ only and capacity $k$. What is $v(1,7)$?
$11$
$3$
$10$
$9$
Explanation. With type $1$ only, $\lfloor 7/2\rfloor=3$ copies fit: $v(1,7)=9$. $11=v(2,7)$ also uses type $2$; $3$ is the value of a single copy.
For the unbounded knapsack (UKP) with $n$ types and capacity $c$, the first DP uses a vector $v(k)$ and the second a table $v(j,k)$. Which comparison is correct?
The first takes $\Theta(nc)$ steps, the second $\Theta(n^2c)$
They have the same number of cells, but the second is exponential
The first has $c+1$ cells, the second $(n+1)(c+1)$; both take $\Theta(nc)$ steps
The first takes $\Theta(c)$ steps, the second $\Theta(nc)$
Explanation. The first computes every $v(k)$ with a maximum over $n$ types; the second computes every cell with two terms. The total work is $\Theta(nc)$ in both cases.
In the second DP for the unbounded knapsack (UKP), $v(j,k)$ uses types $1,\dots,j$ and capacity $k$. Why is the base case $v(0,k)=0$ for every $k$, and not $-\infty$ for $k>0$?
Because $-\infty$ cannot be stored in a table
The knapsack need not be filled: with no type available the empty solution is feasible and worth $0$
Because profits are positive, so no value is negative
Because the capacity $k$ is always zero when $j=0$
Explanation. In the UKP it is enough not to exceed the capacity. In rod cutting, where the whole rod must be divided, the same recurrence uses $v(0,\ell)=-\infty$ for $\ell>0$ instead.
In the first DP for the unbounded knapsack (UKP), to compute $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$, which already computed cells are read?
The cells $v(k-w_j)$, one for every type $j$ with $w_j\le k$
Only the cell $v(k-1)$
All the cells $v(0),\dots,v(k-1)$
The cells $v(k-w_j)$ of the previous row, one per type
Explanation. Every term corresponds to a first copy of type $j$ and reads the value of the residual capacity $k-w_j$; there are at most $n$ terms, hence $\Theta(nc)$ steps.
In the unbounded knapsack (UKP) a type $i$ dominates a type $j$ if $w_i\le w_j$ and $p_i\ge p_j$. What can be done with the dominated type $j$?
Nothing: with unlimited copies no type is dominated
Use it only to fill the residual capacity
Remove type $i$ instead, which has smaller weight
Remove it: each of its copies can be replaced by a copy of $i$ without exceeding the capacity or losing profit
Explanation. Replacing a copy of $j$ by one of $i$ does not increase the weight and does not decrease the profit, so there is an optimal solution without type $j$.
In the unbounded knapsack (UKP) a solution is an integer vector $(x_1,\dots,x_n)$, with $x_j$ copies of type $j$ and $\sum_jw_jx_j\le c$. With $c=10$ and $w=(3,4)$, which bound holds for every component?
$x_1\le3$ and $x_2\le2$, i.e., $x_j\le\lfloor c/w_j\rfloor$
$x_j\le1$
$x_1\le10$ and $x_2\le10$
$x_1+x_2\le1$
Explanation. The copies of a single type already weigh $w_jx_j\le c$: $\lfloor10/3\rfloor=3$, $\lfloor10/4\rfloor=2$. The solutions are therefore finite.
The two DP algorithms for the unbounded knapsack (UKP, unlimited copies of $n$ types, capacity $c$) both perform $\Theta(nc)$ steps. Why do the unlimited copies not increase the number of steps with respect to the 0/1 knapsack?
Because at most one copy per type is considered
Because the capacity is reduced to $\lfloor c/n\rfloor$
The copies increase the steps to $\Theta(nc^2)$
Every state considers one type at a time and reuses values already computed with the same type, without enumerating the number of copies
Explanation. In the recursion, after taking a copy of type $j$ one stays in a state that may take another one: the number of copies is not an explicit loop, unlike the BKP DP ($\Theta(nc\,b_{\max})$).
Unbounded knapsack with $c=10$ and two item types of weights $w=(4,3)$. The candidate solutions are the vectors $(x_1,x_2)$ with $0\le x_j\le\lfloor c/w_j\rfloor$. How many are there?
$121$
$12$
$6$
$4$
Explanation. $\lfloor10/4\rfloor=2$ and $\lfloor10/3\rfloor=3$: $(2+1)(3+1)=12$ candidates, only some of which respect the capacity.
Unbounded knapsack with $c=10$, weights $w=(3,4)$ and profits $p=(5,7)$; a solution is the vector $(x_1,x_2)$ of numbers of copies. Which vector is feasible and what is it worth?
$(2,1)$, weight $10$, profit $17$
$(3,1)$, weight $13$, profit $22$
$(1,2)$, weight $11$, profit $19$
$(0,3)$, weight $12$, profit $21$
Explanation. $2\cdot3+1\cdot4=10\le c$ and $2\cdot5+7=17$; the others exceed the capacity.
In the 0/1 knapsack the solution is a binary vector, in the unbounded knapsack a vector of integers $x_j\in\Z_{\ge0}$. Why are two identical copies in the UKP not counted as two different solutions?
Because in the UKP at most one copy is taken
Because the copies have different weights
Because the capacity is unlimited
The vector records only how many copies of each type are taken, not which copy
Explanation. The copies of a type are indistinguishable: counting subsets of copies would count the same solution several times.
The first DP for the unbounded knapsack computes $v(k)$, the largest profit with capacity $k$, for $k=0,\dots,c$, trying for every $k$ the $n$ item types. With $c=10$ and $n=2$, about how many type evaluations does it perform, and what is the order of the number of steps?
About $2^{10}$; exponential
About $12$; $\Theta(n+c)$
About $20$; $\Theta(nc)$
About $100$; $\Theta(c^2)$
Explanation. For every capacity $k=1,\dots,10$ two types are tried: $20$ evaluations, each in constant time. The InfoSol version adds a vector of choices with a constant number of extra operations.
$v(k)=\max_j\{p_j+v(k-w_j)\}$ with at most one copy per type
$v(k)=v(k-1)+\max_jp_j$
Explanation. One takes a last copy of a type $j$ and reuses the optimal value with capacity $k-w_j$, which may contain further copies of the same type; $v(k-1)$ covers the case of unused capacity.
The second DP for the unbounded knapsack uses a matrix over the types $1,\dots,j$ and the capacities, like the 0/1 knapsack DP, but after taking type $j$ it stays in row $j$. What changes with respect to the 0/1 knapsack DP?
The term «take type $j$» uses $v(j,k-w_j)$ instead of $v(j-1,k-w_j)$, so the type can be taken again
The rows are used in reverse order
The number of steps becomes $\Theta(nc^2)$
Nothing: it is the same recursion
Explanation. Staying in row $j$ allows further copies of the same type; the number of steps stays $\Theta(nc)$ and the InfoSol matrix records the choices for the reconstruction.
The DPs of the unbounded knapsack perform $\Theta(nc)$ steps. If the capacity goes from $c$ to $10c$ (with the same types), how does the number of steps change?
It stays the same
It becomes $100$ times larger
It grows by a single step
It becomes about $10$ times larger
Explanation. The number of steps is linear in the value of $c$: it is pseudo-polynomial, since writing $10c$ needs only a few more bits.
In the DP for the unbounded knapsack, when no type fits into the residual capacity $k$ the value is $v(k)=0$ and not $-\infty$. Which hypothesis is this based on?
The profits are positive
The weights exceed $c$
Each type appears at least once
The capacity may stay unused
Explanation. A solution need not fill the knapsack: with no item the value is $0$; $-\infty$ would mark a subproblem without solutions.
How many steps does the DP $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$ for the unbounded knapsack with $n$ types and capacity $c$ execute, and what kind of time is it?
$\Theta(2^n c)$, exponential
$\Theta(nc)$, pseudo-polynomial
$\Theta(nc)$, polynomial
$\Theta(c^2)$, pseudo-polynomial
Explanation. For each of the $c+1$ capacities $n$ types are examined: $\Theta(nc)$, polynomial in the value $c$ but not in its length.
In the bounded knapsack problem (BKP) type $j$ has $b_j$ available copies of weight $w_j$. In the recurrence, for type $j$ with $b_j=3$, $w_j=4$ and residual capacity $k=10$, how many values of the number of copies $d$ are tried?
$11$ ($d=0,\dots,10$)
$3$ ($d=0,1,2$)
$4$ ($d=0,1,2,3$)
$2$ ($d=1,2$)
Explanation. $d\in\{0,1,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}\}=\{0,1,2\}$: both the bound on the copies and the capacity matter.
In the bounded knapsack problem (BKP) type $j$ has $b_j$ available copies, $b_{\max}=\max_j b_j$, and the capacity is $c$. Which statement on the BKP and its DP is correct?
It generalizes the KP ($b_j=1$) and the UKP ($b_j=\lfloor c/w_j\rfloor$); the DP executes $\Theta(nc\,b_{\max})$ steps
It generalizes the KP ($b_j=1$) but not the UKP; the DP executes $\Theta(nc\,b_{\max})$ steps
It generalizes the KP ($b_j=1$) and the UKP ($b_j=\lfloor c/w_j\rfloor$); the DP executes $\Theta(nc)$ steps
It is a special case of the KP; the DP is polynomial because $b_{\max}\le n$
Explanation. With one copy per type we get the KP, with $\lfloor c/w_j\rfloor$ copies the UKP. The innermost loop tries up to $b_{\max}+1$ values, hence $\Theta(nc\,b_{\max})$, pseudo-polynomial.
In the DP of the bounded knapsack problem (BKP), $s[j][k]$ is the number of copies of type $j$ (weight $w_j$) chosen in the state with types $1,\dots,j$ and capacity $k$. In the reconstruction, after reading $s[j][k]$, how are the indices updated?
$k\leftarrow k-s[j][k]$, and $j$ decreases by $1$
$k\leftarrow k-w_j$, and $j$ stays the same
$k$ stays the same, and $j$ decreases by $s[j][k]$
$k\leftarrow k-s[j][k]\,w_j$, and $j$ decreases by $1$
Explanation. The $s[j][k]$ chosen copies are removed, each of weight $w_j$; the type index always decreases by one.
In the bounded knapsack (BKP) type $j$ has $b_j$ available copies. With $b=(2,2,1,1,1,1)$, how many vectors $(x_1,\dots,x_6)$ with $0\le x_j\le b_j$ are there, before checking the capacity?
$144$
$64$
$8$
$256$
Explanation. Every type has $b_j+1$ choices: $3\cdot3\cdot2^4=144$. $2^6=64$ are the choices with at most one copy per type.
In the bounded knapsack (BKP: profits $p_j$, weights $w_j$, available copies $b_j$, capacity $c$), how is a feasible solution encoded?
By a subset of the items of total weight at most $c$
By an integer vector $x\ge 0$ with $\sum_j w_jx_j=c$
By a binary vector $x$ with $\sum_j b_jw_jx_j\le c$
By an integer vector $x$, $0\le x_j\le b_j$, with $\sum_j w_jx_j\le c$
Explanation. $x_j$ counts the copies of type $j$, bounded by $b_j$, and the total weight does not exceed the capacity. The subset is the KP encoding ($b_j=1$).
Bounded knapsack (BKP) with two types: $p=(4,7)$, $w=(2,3)$, copies $b=(3,1)$, capacity $c=7$. With $v(j,k)=\max_{0\le d\le\min\{b_j,\lfloor k/w_j\rfloor\}}\{d\,p_j+v(j-1,k-d\,w_j)\}$ and $v(0,k)=0$, what is $v(2,7)$?
$11$
$16$
$15$
$12$
Explanation. $d=0$: $v(1,7)=3\cdot4=12$; $d=1$: $7+v(1,4)=7+8=15$. The maximum is $15$. With one copy per type (KP) one would get $11$.
In the recursion tree of the DP for the bounded knapsack (BKP), every node is a call $v(j,k)$ and its children are the calls generated by the recurrence. How many children does the node $v(j,k)$ have at most?
$n$, one for every item type
$\min\{b_j,\lfloor k/w_j\rfloor\}+1$, one for every number of copies of type $j$
$2$, as in the KP
$b_j$, one for every available copy
Explanation. The values $d=0,1,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}$ are tried, and each generates the call $v(j-1,k-d\,w_j)$. With $b_j=1$ we get the two children of the KP.
In the DP for the bounded knapsack (BKP), $v(j,k)$ is the largest profit with types $1,\dots,j$ and capacity $k$. Which property does every row $v(j,\cdot)$ have?
It is non-decreasing in $k$: with more capacity there are more feasible solutions
It is strictly increasing in $k$
It is constant: the profit does not depend on the capacity
It decreases when $k$ exceeds $\sum_j b_jw_j$
Explanation. A feasible solution with capacity $k$ is feasible with capacity $k+1$ too, because the knapsack need not be filled; the value may however stay the same for several consecutive capacities.
In the DP for the bounded knapsack (BKP), $v(j,k)$ is the largest profit with types $1,\dots,j$ and capacity $k$. What is the base case $v(0,k)$, for $k=0,\dots,c$?
$-\infty$ for $k\ge 1$
$k$ for every $k$
$+\infty$ for $k\ge 1$
$0$ for every $k$
Explanation. With no type available the only solution is the empty knapsack, feasible for every capacity and with profit $0$.
A bounded knapsack (BKP) can be transformed into a 0-1 knapsack with $\sum_j b_j$ items, one per copy. How many steps does the KP DP take on the transformed instance, with capacity $c$?
$\Theta(2^{\sum_j b_j})$, exponential
$\Theta(c\,b_{\max})$, independent of $n$
$\Theta(c\sum_j b_j)$, at most $\Theta(nc\,b_{\max})$ as the direct DP
$\Theta(nc)$, independent of the copies
Explanation. The KP DP takes $\Theta(n'c)$ steps with $n'=\sum_j b_j\le n\,b_{\max}$ items: the same order, in the worst case, as the direct BKP DP.
In the bounded knapsack (BKP: type $j$ with weight $w_j$ and $b_j$ copies, capacity $c$), when does the bound $b_j$ never constrain the solution?
When $b_jw_j<c$
When $b_j\ge\lfloor c/w_j\rfloor$: more copies would not fit anyway
When $b_j=1$
When $b_j\le\lfloor c/w_j\rfloor$
Explanation. With $b_j\ge\lfloor c/w_j\rfloor$ the capacity already imposes $x_j\le\lfloor c/w_j\rfloor$: if this holds for every type, the BKP is an unbounded knapsack.
In the DP for the bounded knapsack (BKP) the recurrence tries $d=0,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}$ copies of type $j$. What does it reduce to if $b_j=1$ for every type?
To the 0-1 knapsack DP: $v(j,k)=\max\{v(j-1,k),\ p_j+v(j-1,k-w_j)\}$
To the unbounded knapsack DP: $v(j,k)=\max\{v(j-1,k),\ p_j+v(j,k-w_j)\}$
To the subset sum DP, with boolean values
To a recurrence with a single term, $v(j-1,k)$
Explanation. With $b_j=1$ only the choices $d=0$ and $d=1$ remain, i.e., exclude or take item $j$, and the next row starts from $j-1$ in both cases.
In the bounded knapsack (BKP) a solution is a vector $(x_1,\dots,x_n)$ with integer $0\le x_j\le b_j$ and $\sum_jw_jx_j\le c$. With $n=3$ types and $b=(1,2,4)$, how many candidate vectors are there (before checking the capacity)?
$30$
$128$
$7$
$8$
Explanation. $(b_1+1)(b_2+1)(b_3+1)=2\cdot3\cdot5=30$. $2^7=128$ would treat the $7$ copies as distinct items.
The DP for the bounded knapsack (BKP) performs $\Theta(nc\,b_{\max})$ steps, with $b_{\max}=\max_jb_j$. Why can one assume $b_{\max}\le c$ without loss of generality?
Because in the BKP always $b_j=1$
Because the DP ignores the types with $b_j>c$
It cannot: $b_{\max}$ may exceed $c$ and the bound grows
Replacing $b_j$ by $\min\{b_j,\lfloor c/w_j\rfloor\}$ does not change the problem, since more copies do not fit
Explanation. With $w_j\ge1$ at most $\lfloor c/w_j\rfloor\le c$ copies of type $j$ fit in the knapsack; after the reduction the bound $\Theta(nc\,b_{\max})$ is at most $\Theta(nc^2)$.
A bounded knapsack with $b=(1,2,4)$ available copies of the three types can be turned into a 0/1 knapsack by listing every copy as an item of its own. How many items does the equivalent 0/1 knapsack have?
$3$
$8$
$30$
$7$
Explanation. $1+2+4=7$ items; the transformation is correct but counts equivalent solutions several times, hence the interest in a DP on the BKP.
In the DP for the bounded knapsack, for every pair (type $j$, capacity $k$) the innermost loop tries $d=0,1,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}$ copies. With $k=7$, $w_j=2$ and $b_j=5$, how many iterations does it perform?
$3$
$8$
$4$
$6$
Explanation. $\min\{5,\lfloor7/2\rfloor\}=3$, hence $d=0,1,2,3$: $4$ iterations. In the worst case they are $b_{\max}+1$ per pair, hence $\Theta(nc\,b_{\max})$.
The DP for the bounded knapsack performs in the worst case $S=3n(c+1)(b_{\max}+1)+3n(c+1)+n+2c+4$ steps. How many are they for $n=2$, $c=4$ and $b_{\max}=2$?
$44$
$134$
$90$
$120$
Explanation. $3\cdot2\cdot5\cdot3=90$, $3\cdot2\cdot5=30$, then $2+8+4$: overall $134$. $90$ is only the dominant term.
The bounded knapsack (BKP) has $n$ types, at most $b_j$ copies of type $j$, capacity $c$ and $b_{\max}=\max_j b_j$. How many steps does the DP trying every number of copies execute?
$\Theta(n\,b_{\max})$
$\Theta(c\,b_{\max}^{\,n})$
$\Theta(nc\,b_{\max})$
$\Theta(nc)$
Explanation. $(n+1)(c+1)$ cells, each with up to $b_{\max}+1$ comparisons.
In subset sum (integers $w_1,\dots,w_n$, target $c$), the DP computes $r(j,k)$, true if some subset of $\{w_1,\dots,w_j\}$ sums to exactly $k$. What are the base cases?
$r(j,0)=\textit{true}$ for every $j$, and $r(0,k)=\textit{false}$ for $k\ge 1$
$r(j,0)=\textit{false}$ for every $j$, and $r(0,k)=\textit{true}$ for $k\ge 1$
$r(0,k)=\textit{true}$ for every $k$
$r(j,0)=\textit{false}$ and $r(0,k)=\textit{false}$
Explanation. The value $0$ is always obtained with the empty subset; without items no positive value is reachable. With $r(j,0)=\textit{false}$ no cell would ever become true.
In subset sum (integers $w_1,\dots,w_n$, target $c$), $r(j,k)$ is true if some subset of $\{w_1,\dots,w_j\}$ sums to exactly $k$. Once the table is computed, where is the answer read?
In cell $r(c,n)$
In any true cell of column $c$
In the last true cell of row $n$
In cell $r(n,c)$
Explanation. The answer is $r(n,c)$; a true cell in another column only says that another value is reachable. If $r(n,c)$ is false there is nothing to reconstruct.
In the DP for subset sum, $r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)$ (the second term only if $w_j\le k$). What does the term $r(j-1,k-w_j)$ represent?
The choice of not using weight $w_j$
The choice of using weight $w_j$ twice
The check that $k$ does not exceed the target $c$
The choice of using weight $w_j$: the rest $k-w_j$ must come from the first $j-1$ weights
Explanation. If $w_j$ is in the subset, the previous weights must sum to $k-w_j$; $r(j-1,k)$ is instead the choice of excluding it. Every weight is used at most once.
In the DP for subset sum ($r(j,k)$ true if a subset of the first $j$ weights sums to $k$), with $r(n,c)$ true, how is a subset of sum $c$ rebuilt starting from $(j,k)=(n,c)$?
If $r(j-1,k)$ is true take $w_j$; otherwise exclude it
Take the largest weight and restart with $c-w_{\max}$
If $r(j-1,k)$ is true exclude $w_j$; otherwise take $w_j$ and set $k\leftarrow k-w_j$; then $j\leftarrow j-1$
Take the weights $w_j$ in order until the sum exceeds $c$
Explanation. If $k$ is already reachable without $w_j$, it can be excluded; otherwise the cell is true thanks to $r(j-1,k-w_j)$ and $w_j$ must be taken. One ends at $k=0$.
Subset sum with weights $w=(4,6,9)$ and target $c=12$. The DP computes $r(3,k)$ for $k=0,\dots,12$ ($r(j,k)$ true if a subset of the first $j$ weights sums to exactly $k$). What is the largest $k\le 12$ with $r(3,k)$ true?
$13$
$10$
$12$
$9$
Explanation. The reachable sums are $0,4,6,9,10,13,15,19$; among those not above $12$ the largest is $10=4+6$. $13=4+9$ exceeds the target.
The DP for subset sum can be implemented with a single vector $r[0..c]$, updated weight by weight with $r[k]\leftarrow r[k]\lor r[k-w_j]$. In which order are the sums $k$ scanned?
From $c$ down to $w_j$, decreasing, so as not to use the same weight twice
From $w_j$ up to $c$, increasing, to read already updated cells
In any order, because the operation is an «or»
Only the sums that are multiples of $w_j$
Explanation. Scanning increasingly, $r[k-w_j]$ could already be true thanks to $w_j$ itself, which would be used several times: that is the order of the unbounded knapsack, not of subset sum.
In subset sum (weights $w_1,\dots,w_n$, target $c$), the DP fills the table $r(j,k)$ for $j=0,\dots,n$ and $k=0,\dots,c$. How many cells does it have with $n=5$ and $c=20$?
$100$
$105$
$32$
$126$
Explanation. $(n+1)(c+1)=6\cdot 21=126$. $2^5=32$ counts the subsets; $100$ and $105$ forget row $0$ or column $0$.
The DP for subset sum takes $\Theta(nc)$ steps with $n$ weights and target $c$. Why does subset sum remain NP-complete?
Because the number of subsets is $2^n$, and the DP lists them all
Because the table has boolean values instead of integers
$c$ is written with about $\log_2 c$ digits, and $\Theta(nc)$ is exponential in that number of digits
Because the DP is correct only for distinct weights
Explanation. The time is polynomial in the value of $c$ but not in the input length: it is a pseudo-polynomial algorithm, and subset sum is weakly NP-complete.
Subset sum (weights $w_j$, target $c$) is the 0-1 knapsack with profits $p_j=w_j$ and capacity $c$. With the KP DP, $v(n,c)$ is the largest weight of a subset not exceeding $c$. How is the subset sum answer read?
It is yes if and only if $v(n,c)=\sum_j w_j$
It is yes if and only if $v(n,c)=c$
It is yes if and only if $v(n,c)\ge 1$
It is yes if and only if $v(n,c)\le c$
Explanation. A subset of sum exactly $c$ exists if and only if the largest weight not above $c$ equals $c$; $v(n,c)\le c$ always holds.
The DP for the subset sum (SSP: is there a subset of weights $w_j$ summing exactly to $c$?) fills a table over the items and the values $0,\dots,c$. How many steps does it perform in the worst case, with $n$ items?
$\Theta(nc)$, as the 0/1 knapsack DP
$\Theta(2^n)$
$\Theta(n\log c)$
$\Theta(c^2)$
Explanation. One cell per (item, value) pair with a constant number of operations: $\Theta(nc)$, pseudo-polynomial as for the KP; the reconstruction adds $\Theta(n)$ steps.
The DP for the subset sum fills a table with one row per prefix of items $0,1,\dots,n$ and one column per value $0,\dots,c$. With $n=4$ and $c=10$, how many cells does it have?
$44$
$16$
$55$
$40$
Explanation. $(4+1)(10+1)=55$ cells, each computed in constant time: $\Theta(nc)$.
After filling the table of the subset sum DP, a subset of sum $c$ is reconstructed going back from cell $(n,c)$. How many steps does the reconstruction need?
$\Theta(2^n)$
$\Theta(n)$: one step per item
$\Theta(nc)$
$\Theta(c)$
Explanation. For every item, from the last to the first, one decides whether it was used by looking at one cell of the previous row.
Subset sum asks whether some subset has weight exactly $c$. Let $z$ be the optimal value of the 0/1 knapsack with $p_j=w_j$ and capacity $c$. When is the answer «yes»?
If and only if $z\ge c/2$
If and only if $z<c$
Never: the problems are unrelated
If and only if $z=c$
Explanation. With $p_j=w_j$ profit is weight: the maximum weight up to $c$ equals $c$ exactly when some subset weighs $c$.
In the multiple-choice knapsack problem (MCKP: $q$ classes, exactly one item per class, capacity $c$), $v(h,k)$ is the optimal value with classes $1,\dots,h$ and capacity $k$. What are $v(0,k)$ and the value of a subproblem without feasible solutions?
$v(0,k)=0$ for every $k$; without feasible solutions it is $0$
$v(0,k)=-\infty$ for $k\ge 1$; without feasible solutions it is $0$
$v(0,k)=k$ for every $k$; without feasible solutions it is $+\infty$
$v(0,k)=0$ for every $k$; without feasible solutions it is $-\infty$
Explanation. With no class the empty set is feasible for every capacity; $-\infty$ marks the subinstances in which a class has no item that fits. With $0$ a class would be skipped.
In the multiple-choice knapsack problem (MCKP, classes $\mathscr{J}_1,\dots,\mathscr{J}_q$) the recurrence is $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$. What is missing with respect to the 0/1 KP recurrence?
The base case $v(0,k)$, because the first class replaces it
The check $w_j\le k$, because the class fixes the weight
The term $v(h-1,k)$, because every class gives exactly one item
The term $v(h-1,k)$, because no item has zero weight
Explanation. In the KP an item can be left out; in the MCKP exactly one item is taken from every class, so the option «none» does not appear.
In the multiple-choice knapsack problem (MCKP) the $n$ items are partitioned into the classes $\mathscr{J}_1,\dots,\mathscr{J}_q$ and the capacity is $c$. How many steps does the DP with the classes as stages execute?
Multiple-choice knapsack (MCKP): classes $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4\}$, profits $p=(3,5,4,6)$, weights $w=(2,4,1,3)$, capacity $c=5$; exactly one item per class is chosen. With $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$, what is $v(2,5)$?
$7$
$10$
$9$
$11$
Explanation. The feasible pairs are $\{1,3\}$ (weight $3$, profit $7$), $\{1,4\}$ and $\{2,3\}$ (weight $5$, profit $9$); $\{2,4\}$ weighs $7$. The value $11=5+6$ ignores the capacity.
Multiple-choice knapsack (MCKP) with classes $\mathscr{J}_1=\{1,2\}$ (weights $2$ and $4$) and $\mathscr{J}_2=\{3,4\}$ (weights $1$ and $3$); exactly one item per class is chosen. What does the DP give with capacity $c=2$?
The profit of the lightest item of class $2$
$v(2,2)=-\infty$: there is no feasible solution
$v(2,2)=0$: no item is chosen
The profit of the lightest item of class $1$
Explanation. At least $2+1=3$ units of capacity are needed, one item per class: with $c=2$ no choice is feasible. In a maximization problem the value $-\infty$ flags infeasibility.
In the DP for the multiple-choice knapsack (MCKP), $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$. How many subproblems does state $(h,k)$ generate at most?
$|\mathscr{J}_h|$, one per item of class $h$ that fits
$2$, as in the 0/1 KP
$|\mathscr{J}_h|+1$, counting the choice of no item
$q$, one per class
Explanation. Every item of class $h$ with $w_j\le k$ is a possible choice; there is no «no item» choice, because every class gives exactly one item.
In the DP for the multiple-choice knapsack (MCKP), $s(h,k)$ is the item of class $h$ attaining the maximum in $v(h,k)$. How is an optimal solution rebuilt starting from $(q,c)$?
Choose $s(q,c)$ and repeat it for every class
Choose in every class the item of largest profit
Choose $j=s(h,k)$ and set $h\leftarrow h-1$ without changing $k$
Choose $j=s(h,k)$, set $k\leftarrow k-w_j$ and $h\leftarrow h-1$, until $h=0$
Explanation. Every step fixes the item of one class and reduces the residual capacity by its weight; exactly one item per class is obtained.
In the DP for the multiple-choice knapsack (MCKP) with $q$ classes and capacity $c$, the table $v(h,k)$ has one row for every $h=0,\dots,q$ and one column for every $k=0,\dots,c$. How many cells does it have with $q=3$ and $c=15$?
$96$
$45$
$64$
$48$
Explanation. $(q+1)(c+1)=4\cdot16=64$. The rows are the classes, not the items: this is why the steps are $\Theta(c\sum_h|\mathscr{J}_h|)=\Theta(nc)$.
Multiple-choice knapsack (MCKP): class $\mathscr{J}_1$ contains the items $(p,w)=(3,2)$ and $(5,4)$; exactly one item per class is chosen. What is $v(1,3)$, the optimal value with class $1$ only and capacity $3$?
$0$
$3$
$5$
$-\infty$
Explanation. With capacity $3$ only the item of weight $2$ fits: $v(1,3)=3$. For $k<2$ the class gives no item and $v(1,k)=-\infty$; the value $0$ would mean choosing nothing, which is forbidden.
In the DP for the multiple-choice knapsack (MCKP), what is the base case $v(0,k)$, with no class considered and capacity $k\ge 0$?
$-\infty$ for every $k\ge 1$
$-\infty$ for $k=0$ and $0$ otherwise
$k$ for every $k$
$0$ for every $k$: the empty choice is feasible when there are no classes
Explanation. With zero classes there is nothing to choose, and capacity may stay unused. The value $-\infty$ appears only when a class has no item that fits.
In the DP for the multiple-choice knapsack (MCKP) the classes are the stages of the recursion. What happens to the optimal value if the order of the classes is changed?
It changes, unless the classes are sorted by profit
It does not change, but the DP becomes incorrect
It does not change: only the intermediate values of the table change
It changes, because the first class has more capacity available
Explanation. A solution is one item per class, and its profit and weight do not depend on the order; every order gives a correct recurrence with the same final value.
The DP for the multiple-choice knapsack (MCKP: $q$ classes $\mathscr{J}_h$, exactly one item per class, capacity $c$) performs $\Theta(c(|\mathscr{J}_1|+\dots+|\mathscr{J}_q|))$ steps. With $3$ classes of $4$, $2$ and $6$ items and $c=50$, what is the order of the number of steps?
$2^{12}$ times a constant
$12\cdot50=600$ times a constant
$4\cdot2\cdot6\cdot50=2400$ times a constant
$3\cdot50=150$ times a constant
Explanation. For every class and every capacity the items of the class are tried: overall $n\,c$ with $n=12$ items. The product $4\cdot2\cdot6$ counts the choices of one item per class, which the DP does not enumerate.
After computing the table of the DP for the multiple-choice knapsack ($q$ classes, one item per class), how many steps does the reconstruction of the solution need?
$\Theta(qc)$
$\Theta(2^q)$
$\Theta(q)$: one step per class
$\Theta(n)$: one step per item
Explanation. Going back from capacity $c$ one reads, class by class, the chosen item: one step per class.
The multiple-choice knapsack has $q$ classes $\mathscr{J}_h$, $n=\sum_h|\mathscr{J}_h|$ items and capacity $c$. How many steps does the DP over the classes execute, and when is the instance infeasible?
$\Theta(nc)$; if $v(q,c)=0$
$\Theta(n^2c)$; if $v(q,0)=-\infty$
$\Theta(nc)$; if $v(q,c)=-\infty$
$\Theta(qc)$; if $v(q,c)=0$
Explanation. Each cell $(h,k)$ examines the items of class $h$: $\Theta(c\sum_h|\mathscr{J}_h|)=\Theta(nc)$ in total.
7. DP for the multidimensional knapsack problem (17)
In the multidimensional knapsack problem (MDKP) every item has a weight vector and the knapsack a capacity vector $\vet{c}$. How many cells does the DP table $v(j,\vet{k})$ have with $n=4$ items and $\vet{c}=(5,4)$?
$50$
$150$
$120$
$45$
Explanation. The cells are $(n+1)\prod_d(c_d+1)=5\cdot 6\cdot 5=150$: one vector of residual capacities for every $j\in\{0,\dots,n\}$.
In the multidimensional knapsack problem (MDKP) item $j$ has weights $w_{dj}$ in the dimensions $d=1,\dots,m$. In the DP, when does item $j$ «fit» into the residual capacity vector $\vet{k}$?
When $w_{dj}\le k_d$ for every dimension $d$
When $w_{dj}\le k_d$ for at least one dimension $d$
When $\sum_d w_{dj}\le\sum_d k_d$
When $\max_d w_{dj}\le\min_d k_d$
Explanation. The vector $\vet{w}_j$ must fit into $\vet{k}$ component by component; if the item is selected, all the components of $\vet{k}$ decrease.
Multidimensional knapsack (MDKP) with capacities $\vet c=(4,4)$ and three items: profits $p=(5,4,3)$, weights in dimension 1 $(3,1,2)$ and in dimension 2 $(1,3,2)$; every item at most once. What is the optimal value $v(3,(4,4))$?
$5$
$7$
$9$
$12$
Explanation. $\{1,2\}$ weighs $(4,4)$ and is worth $9$; $\{1,3\}$ weighs $5$ in dimension 1 and $\{2,3\}$ weighs $5$ in dimension 2. $7$ comes from looking only at dimension 1 for $\{2,3\}$.
In the DP for the multidimensional knapsack (MDKP), $v(j,\vet k)$ is the largest profit with items $1,\dots,j$ and residual capacity vector $\vet k$; $\vet w_j$ is the weight vector of item $j$. Which recurrence is correct?
$v(j,\vet k)=p_j+v(j-1,\vet k-\vet w_j)$ if $\sum_d w_{dj}\le\sum_d k_d$
Explanation. It is the KP recurrence with a vector instead of the capacity: the item is taken only if it fits in every dimension. Staying in row $j$ would allow several copies.
In the DP for the multidimensional knapsack with $m=10$ dimensions, all of capacity $100$, how many residual capacity vectors $\vet k$ are there for every item?
$101^{10}$
$10\cdot 101$
$100^{10}$
$2^{10}$
Explanation. Every component ranges from $0$ to $100$: $\prod_d(c_d+1)=101^{10}\approx 10^{20}$ states per row. It is the curse of dimensionality: the number of states grows exponentially with $m$.
In the DP for the multidimensional knapsack (MDKP), what is the base case $v(0,\vet k)$, with no items and residual capacity vector $\vet k\ge\vet 0$?
$-\infty$ for $\vet k\ne\vet 0$
$\sum_d k_d$
$+\infty$ for every $\vet k$
$0$ for every $\vet k$
Explanation. With no items the empty solution is feasible for every capacity vector and is worth $0$; the knapsack need not be filled in any dimension.
In the DP for the multidimensional knapsack (MDKP), when rebuilding an optimal solution from $(n,\vet c)$, how is the state updated when item $j$ is chosen?
$j$ stays and $\vet k\leftarrow\vet k-\vet w_j$
$j\leftarrow j-1$ and $\vet k$ stays
$j\leftarrow j-1$ and $\vet k\leftarrow\vet k-\vet w_j$, i.e., every component decreases by the item weight in that dimension
$j\leftarrow j-1$ and only the first component of $\vet k$ decreases
Explanation. The item consumes capacity in all dimensions: its weight vector is subtracted and we move to the previous item.
The multidimensional knapsack (MDKP) has $m$ dimensions, with a weight $w_{dj}$ and a capacity $c_d$ per dimension. What does it reduce to with $m=1$, and what does its DP become?
To the multiple knapsack, with a capacity vector
To the 0-1 knapsack, with the DP $v(j,k)$ on a single capacity
To the unbounded knapsack, with the DP $v(k)$
To subset sum, with the boolean DP
Explanation. With one dimension a single capacity constraint remains and the table $v(j,\vet k)$ becomes $v(j,k)$: the KP DP is the case $m=1$.
In the DP for the multidimensional knapsack (MDKP) with $n$ items and capacities $c_1,\dots,c_m$, how many steps are taken?
$\Theta\big(n\prod_d(c_d+1)\big)$: pseudo-polynomial only for fixed $m$
$\Theta\big(n\sum_d c_d\big)$: pseudo-polynomial for every $m$
$\Theta(nm)$: polynomial
$\Theta(2^n)$: as brute force
Explanation. Every cell $v(j,\vet k)$ is computed with two terms, and the cells are $(n+1)\prod_d(c_d+1)$; the product makes the time exponential in the number of dimensions.
In the DP for the multidimensional knapsack (MDKP), the table $v(j,\vet k)$ has one cell for every $j=0,\dots,n$ and every vector $\vet 0\le\vet k\le\vet c$. How many cells does it have with $n=3$ and $\vet c=(4,4)$?
$75$
$48$
$64$
$100$
Explanation. $(n+1)(c_1+1)(c_2+1)=4\cdot5\cdot5=100$. $75$ forgets row $j=0$; $48=4\cdot4\cdot3$ forgets the zero capacities.
For the multidimensional knapsack (MDKP) with two dimensions of capacity $c_1$ and $c_2$ and $n$ items, how many steps does the DP take, and how does it compare with the 0-1 knapsack DP with capacity $c$?
$\Theta(n^2c_1c_2)$, because there are two dimensions
$\Theta(nc_1)$, because the most binding dimension is enough
$\Theta(n\,c_1c_2)$, against $\Theta(nc)$: a second dimension multiplies the work by its capacity
$\Theta(n(c_1+c_2))$, the same order as the 0-1 knapsack
Explanation. The states per row are $(c_1+1)(c_2+1)$, each with two terms. Using only the most binding dimension would give a relaxation, not the optimal value.
The DP for the multidimensional knapsack (MDKP: $m$ capacities $c_d$) has one state for every capacity vector $\vet k$, i.e., $N=\prod_d(c_d+1)$ states per item. With $m=2$, $\vet c=(10,20)$ and $n=5$ items, how many states per item are there?
$32$
$231$
$30$
$200$
Explanation. $N=(10+1)(20+1)=231$, and the steps are $\Theta(m\,n\,N)$. $30$ adds the capacities, which is the typical mistake: the states multiply.
The DP for the multidimensional knapsack performs $\Theta(m\,n\prod_{d=1}^m(c_d+1))$ steps. Under which assumption is this number pseudo-polynomial?
If the number $m$ of dimensions is fixed: then it is $\Theta(n\prod_dc_d)$, polynomial in the values of the capacities
Always, for every $m$
Only if all capacities are equal
Only if $n\le m$
Explanation. With $m$ part of the input the product of the capacities is exponential in $m$ even with small capacities (e.g., $2^m$ with $c_d=1$): it is the curse of dimensionality.
In the DP for the multidimensional knapsack the state is a capacity vector $\vet k$, with $\prod_d(c_d+1)$ values. With $m=10$ dimensions and all capacities $c_d=1$, how many states are there per item?
$11$
$100$
$1024$
$20$
Explanation. $2^{10}=1024$: even with minimal capacities the number of states grows exponentially with the dimensions. It is the curse of dimensionality.
The DP for the multidimensional knapsack (MDKP) with $m$ dimensions and capacities $c_1,\dots,c_m$ executes $\Theta(m\,n\prod_d(c_d+1))$ steps. What happens as $m$ grows?
The time becomes polynomial
The number of states does not change
The states grow exponentially in $m$
The time grows linearly in $m$
Explanation. The product of the $m$ capacities explodes: the curse of dimensionality.
In the knapsack problem with setups (KPS) the items are in classes; using class $h$ costs a setup profit $f_h$ and a setup weight $s_h$. In the DP, $v(h,k)$ is the optimal value with classes $1,\dots,h$ and $u(h,\cdot,k)$ are the rows of the open class $h$. How is the setup paid?
Once, in the row $u(h,0,k)=v(h-1,k-s_h)-f_h$
Once for every chosen item of the class, subtracting $f_h$ and $s_h$
Once, in the row $v(h,k)$, if $v(h,k)>v(h-1,k)$
Once, at the end, subtracting $\sum_h f_h$ from $v(q,c)$
Explanation. The row $u(h,0,\cdot)$ opens the class: it reserves the setup weight $s_h$ and subtracts the cost $f_h$; the following rows are the KP recurrence over the items of the class.
In the DP of the knapsack problem with setups (KPS), $v(h,k)$ is the optimal value with classes $1,\dots,h$ and capacity $k$, and $u(h,t_h,k)$ the value with class $h$ open (setup paid) after its $t_h$ items. How is $v(h,k)$ computed for $h\ge 1$?
$v(h,k)=v(h-1,k)+u(h,t_h,k)$
$v(h,k)=\max\{v(h-1,k),\ u(h,0,k)\}$
$v(h,k)=u(h,t_h,k)$
$v(h,k)=\max\{v(h-1,k),\ u(h,t_h,k)\}$
Explanation. For every class the two options are compared: not using it (value $v(h-1,k)$) or opening it and choosing its items (value $u(h,t_h,k)$).
In the DP of the knapsack problem with setups (KPS: class $h$ has setup cost $f_h$ and setup weight $s_h$), why do the rows of the items of class $h$ not start from $v(h-1,k)$, the optimal value with the previous classes?
Because $v(h-1,k)$ is not yet computed at that point
Because $v(h-1,k)$ equals $-\infty$ when $s_h>0$
Because items of the class would be chosen without paying its setup
Because the setup would be paid once for every chosen item
Explanation. The rows of an open class start from $u(h,0,k)=v(h-1,k-s_h)-f_h$, which has already paid the setup once.
Knapsack with setups (KPS) with a single class: setup cost $f=3$, setup weight $s=2$, items $(p,w)=(5,2)$ and $(4,3)$, capacity $c=6$. The setup is paid once if at least one item of the class is chosen. What is the optimal value?
$5$
$6$
$0$
$2$
Explanation. Once the class is open $6-2=4$ units remain: only $(5,2)$ fits, since the two items weigh $5$. The value is $5-3=2>0$. $5$ forgets the setup cost, $6=9-3$ forgets the setup weight.
In the DP for the knapsack with setups (KPS), $u(h,0,k)=v(h-1,k-s_h)-f_h$ is the value with class $h$ open (setup paid) and none of its items chosen yet. What is it if $k<s_h$?
$-f_h$: the setup is paid without capacity
$v(h-1,k)$: the setup is ignored
$-\infty$: the class cannot be opened because the setup weight does not fit
$0$: the class stays closed
Explanation. Opening the class consumes $s_h$ units of capacity; if they are not available, the state is unreachable and $-\infty$ excludes it from the maximum.
In the DP for the knapsack with setups (KPS), opening class $h$ without choosing items gives $u(h,0,k)=v(h-1,k-s_h)-f_h$. Why does this state alone never improve $v(h,k)=\max\{v(h-1,k),\ u(h,t_h,k)\}$?
Because $v(h-1,k-s_h)-f_h\le v(h-1,k)$: the setup is paid and capacity lost with no gain
Because $u(h,0,k)$ is always $-\infty$
Because class $h$ has at least one item with positive profit
Because $f_h$ is always larger than $s_h$
Explanation. $v(h-1,\cdot)$ is non-decreasing in the capacity and $f_h\ge 0$: an open but empty class does not pay off. The state is the starting point of the rows of the items of the class.
In the DP for the knapsack with setups (KPS) with $q$ classes, $n$ items in total and capacity $c$, there is one row $v(h,\cdot)$ per class and one row $u(h,i,\cdot)$ for every item and for the opening of every class. How many steps are taken?
$\Theta(nqc)$
$\Theta(2^qnc)$
$\Theta(nc^2)$
$\Theta((n+q)c)$
Explanation. The rows are $O(n+q)$, each with $c+1$ cells computed in constant time: $\Theta((n+q)c)$, pseudo-polynomial as the KP DP.
In the DP for the knapsack with setups (KPS), when rebuilding an optimal solution, what is decided in state $(h,k)$ before looking at the items of class $h$?
How many classes to open in total
Whether the setup weight $s_h$ exceeds the total capacity $c$
Whether class $h$ is open, comparing $v(h,k)$ with $v(h-1,k)$
Which item of class $h$ has the largest profit
Explanation. If $v(h,k)=v(h-1,k)$ the class can stay closed and we move to $h-1$ with the same capacity; otherwise the rows $u(h,\cdot,\cdot)$ of the items are scanned and finally the setup weight is removed.
In the knapsack with setups (KPS), class $h$ has setup cost $f_h$ and its items have total profit $P_h$. When is the class never opened in an optimal solution, whatever the capacity?
When the class has a single item
When $f_h\ge P_h$: even taking all the items the net gain is not positive
When $f_h\le P_h$
When the setup weight is zero
Explanation. Opening the class yields at most $P_h-f_h\le 0$ and consumes capacity: keeping it closed never worsens the solution.
In the DP for the knapsack with setups (KPS), after opening class $h$ the rows $u(h,i,k)$ scan its items. Which recurrence do they use, with $j$ the $i$-th item of the class?
$u(h,i,k)=\max\{v(h-1,k),\ p_j+v(h-1,k-w_j)\}$
$u(h,i,k)=p_j-f_h+u(h,i-1,k-w_j-s_h)$
$u(h,i,k)=\max\{u(h,i-1,k),\ p_j+u(h,i,k-w_j)\}$
$u(h,i,k)=\max\{u(h,i-1,k),\ p_j+u(h,i-1,k-w_j)\}$, as in the 0/1 KP
Explanation. Inside the open class every item is taken or not, once; the setup is already paid in row $u(h,0,\cdot)$, so it does not appear any more.
The DP for the knapsack with setups (KPS: $n$ items in $q$ classes with setup cost and weight, capacity $c$) performs $\Theta(nc)$ steps. What do the setups add with respect to the 0/1 knapsack DP?
Nothing: the setups are ignored
A number of rows proportional to $q$ (opening and closing every class), absorbed by $\Theta(nc)$ since $q\le n$
A factor $2^q$ for the activated classes
A factor $q$, i.e., $\Theta(nqc)$
Explanation. For every class the table has two more rows (class closed or activated) besides the item rows: $\Theta((n+2q)c)=\Theta(nc)$.
In the multiple knapsack problem (MKP) there are $m$ knapsacks of capacities $c_1,\dots,c_m$ and every item goes into at most one knapsack. In the DP, if item $j$ is inserted into knapsack $i$, how does the residual capacity vector $\vet{k}$ change?
All the components decrease, by $w_j$
All the components decrease, by $w_j/m$
It does not change: capacities are checked at the end
Only the component $k_i$ decreases, by $w_j$
Explanation. The item goes into one knapsack only: $\vet{k}-w_j\vet{e}_i$. Decreasing all the components is the rule of the multidimensional knapsack.
In the multiple knapsack problem (MKP: $m$ knapsacks, every item in at most one knapsack), the DP has states $(j,\vet{k})$ with $\vet{k}$ the residual capacity vector. At most how many subproblems does state $(j,\vet{k})$ generate?
$2$: item $j$ is chosen or not, regardless of the knapsack
$m$: item $j$ always goes into one of the knapsacks where it fits
$m+1$: item $j$ stays out or goes into one of the knapsacks where it fits
$2^m$: one for every subset of knapsacks to put item $j$ into
Explanation. The option «item left out» ($v(j-1,\vet{k})$) is always present; in addition there is one option for every knapsack $i$ with $w_j\le k_i$.
In the multiple knapsack problem (MKP: $m$ knapsacks of capacities $c_1,\dots,c_m$, every item in at most one knapsack), what does the optimal value of the KP with a single knapsack of capacity $c_1+\dots+c_m$ give?
The value of a feasible solution of the MKP
An upper bound: the solution may not be divisible among the knapsacks
A lower bound: the solution can always be divided among the knapsacks
The optimal value of the MKP, because the capacities add up
Explanation. Every MKP solution is feasible for the KP with the total capacity, not conversely: we get a relaxation, hence an upper bound.
Multiple knapsack (MKP) with two knapsacks of capacity $c_1=c_2=3$ and three items $(p,w)=(4,2)$, $(4,2)$, $(5,3)$; every item goes into at most one knapsack. What is the optimal value?
$9$
$8$
$13$
$10$
Explanation. Item $3$ fills one knapsack and one of the first two goes into the other: $5+4=9$. The two items of weight $2$ do not fit together in a knapsack of capacity $3$, so $13$ is infeasible.
In the DP for the multiple knapsack (MKP) with $m$ knapsacks, $v(j,\vet k)$ is the optimal value with items $1,\dots,j$ and residual capacities $\vet k=(k_1,\dots,k_m)$, and $\vet e_i$ is the unit vector of knapsack $i$. Which recurrence is correct?
Explanation. Item $j$ stays out or goes into a knapsack $i$ where it fits, and only that capacity decreases. Without the term $v(j-1,\vet k)$ every item would have to be inserted.
In the DP for the multiple knapsack (MKP) with knapsacks of equal capacity, the states $(j,\vet k)$ and $(j,\vet k')$ with $\vet k'$ a permutation of $\vet k$ have the same value. How can this be exploited?
Removing empty knapsacks from the state
It cannot: the DP must distinguish the knapsacks
Keeping only sorted vectors, for example with non-increasing components
Using a single capacity, the sum of the components
Explanation. Identical knapsacks are interchangeable, so one representative per class of permuted vectors suffices: the number of states decreases, although it stays exponential in $m$.
In the DP for the multiple knapsack (MKP) with $m$ knapsacks of capacity $c$ and $n$ items, how does the number of states grow with the number of knapsacks?
As $2^n$, independently of $m$
As $(c+1)^m$ per item: exponentially in $m$
As $m(c+1)$: linearly in $m$
As $c^2$, independently of $m$
Explanation. The state contains one residual capacity per knapsack: $\prod_i(c_i+1)=(c+1)^m$ vectors. This is why the DP is practical only with few knapsacks.
In the DP for the multiple knapsack (MKP), to rebuild an optimal solution a value $s(j,\vet k)$ is stored for every state $(j,\vet k)$. What is best to store?
Only whether item $j$ is chosen or not
The total profit of the fullest knapsack
The vector $\vet k$ of the next state
The index of the knapsack receiving item $j$, with $0$ if it stays out
Explanation. With the index $i$ one updates $\vet k\leftarrow\vet k-w_j\vet e_i$ and knows where the item goes; «chosen or not» is not enough, because an MKP solution also says where.
The multiple knapsack (MKP) has $m$ knapsacks of capacity $c_1,\dots,c_m$ and every item goes into at most one knapsack. What does it reduce to with $m=1$?
To the multidimensional knapsack with one dimension per item
To bin packing with one bin
To the 0-1 knapsack with capacity $c_1$
To the unbounded knapsack with capacity $c_1$
Explanation. With one knapsack every item is in or out, with one capacity: it is the KP, and the DP with the vector $\vet k$ becomes the one with the capacity $k$.
In the DP for the multiple knapsack (MKP), the table $v(j,\vet k)$ has one cell for every $j=0,\dots,n$ and every vector $\vet 0\le\vet k\le\vet c$. How many cells does it have with $n=4$ items and capacities $\vet c=(3,5)$?
$40$
$120$
$96$
$45$
Explanation. $(n+1)(c_1+1)(c_2+1)=5\cdot4\cdot6=120$. $96$ forgets row $j=0$; $45=5\cdot(3+5+1)$ adds the capacities instead of multiplying them.
In the DP for the multiple knapsack (MKP) with $m$ knapsacks, every state $(j,\vet k)$ generates at most $m+1$ subproblems. How many steps does the DP take with $n$ items and capacities $c_1,\dots,c_m$?
$\Theta\big(nm\prod_i(c_i+1)\big)$
$\Theta\big(n\sum_i c_i\big)$
$\Theta\big(n(m+1)\big)$
$\Theta\big(2^m n\big)$
Explanation. The cells are $(n+1)\prod_i(c_i+1)$ and each compares $m+1$ terms. The time is pseudo-polynomial only for fixed $m$.
The DP for the multiple knapsack (MKP: $m$ knapsacks of capacity $c_i$) uses as state the vector of residual capacities, $N=\prod_i(c_i+1)$ states per item, and $\Theta(m\,n\,N)$ steps. With $m=2$ knapsacks of capacity $5$ and $7$, how many states per item are there?
$35$
$12$
$48$
$13$
Explanation. $(5+1)(7+1)=48$. With a single knapsack of capacity $12$ there would be $13$ states: splitting the capacity into two knapsacks multiplies the states.
The DP for the multiple knapsack performs $S=3m\,nN+2nN+2N+n+2$ steps, with $N=\prod_i(c_i+1)$. How many are they with $m=2$ knapsacks of capacity $1$ and $2$ and $n=2$ items?
$72$
$96$
$60$
$112$
Explanation. $N=2\cdot3=6$: $3\cdot2\cdot2\cdot6=72$, $2\cdot2\cdot6=24$, $2\cdot6=12$, then $2+2$: $112$.
In the DP for the multiple knapsack, with $m$ knapsacks, the state is the vector of residual capacities. With $m=3$ knapsacks of capacity $2$, how many states are there per item?
$7$
$8$
$27$
$9$
Explanation. $(2+1)^3=27$: one residual capacity value per knapsack, combined in all ways.
A total capacity of $12$ is split among $m$ equal knapsacks. How many states $\prod_i(c_i+1)$ does the multiple knapsack DP have with $m=1$ (capacity $12$) and with $m=3$ (capacities $4,4,4$)?
$13$ and $39$
$13$ and $125$
$13$ and $15$
$12$ and $64$
Explanation. $12+1=13$ and $5^3=125$: for the same total capacity the states grow exponentially with the number of knapsacks. $39$ adds the states instead of multiplying them.
The DP for the multiple knapsack performs $\Theta(m\,n\prod_i(c_i+1))$ steps. Why is it pseudo-polynomial for a fixed number $m$ of knapsacks, but not when $m$ is part of the input?
For fixed $m$ the product is a polynomial of degree $m$ in the capacities; with variable $m$ the exponent grows with the instance
Because for fixed $m$ the problem is in P
Because the number of items does not count
It is always pseudo-polynomial
Explanation. With $m$ knapsacks of capacity $c$ the states are $(c+1)^m$: a polynomial in $c$ only if $m$ is a constant.
In the DP for the multiple knapsack (MKP) with $m$ knapsacks the state is $(j,\vet{k})$, with $\vet{k}$ the residual capacities. How many choices does item $j$ have, and how many steps does the DP execute?
$m$; $\Theta(n\,m^2)$
$2^m$; $\Theta(n\sum_i c_i)$
$m+1$; $\Theta(m\,n\prod_i(c_i+1))$
$2$; $\Theta(nc)$
Explanation. The item stays out or goes into one of the $m$ knapsacks; there are $n\prod_i(c_i+1)$ states.
In uncapacitated lot sizing (ULS) let $x_t$ be the production and $s_t$ the inventory at the end of period $t$. Which statement is the Wagner-Whitin zero-inventory ordering property?
Every ULS instance has an optimal solution with $s_t\,x_t=0$ for every period $t$
Every ULS instance has an optimal solution with $s_{t-1}\,x_t=0$ for every period $t$
Every optimal solution of the ULS has $s_{t-1}\,x_t=0$ for every period $t$
Every CLS instance has an optimal solution with $s_{t-1}\,x_t=0$ for every period $t$
Explanation. There is an optimal solution in which production happens only when the incoming stock is zero; not all optimal solutions satisfy it, and with capacities the property can fail.
In uncapacitated lot sizing (ULS), the zero-inventory ordering property says that some optimal plan produces only when the incoming inventory is zero. What is needed to prove it?
Non-negative costs and unlimited production, to move production between two periods without increasing the cost
Non-negative costs and constant capacities, to move production between two periods without increasing the cost
Zero holding costs and unlimited production, so that inventory never costs anything
All demands equal and constant setup costs, so that the periods are interchangeable
Explanation. The proof moves production from one period to another without limits: with capacities this is not always possible, and the property fails.
In uncapacitated lot sizing (ULS) with $m$ periods, the Wagner-Whitin algorithm uses the recurrence $v(t)=\min_j\{v(j-1)+c_{j,t}\}$, with $c_{j,t}$ the cost of the lot produced in $j$ for periods $j,\dots,t$. How many steps does it execute, if the $c_{j,t}$ are computed incrementally?
$\Theta(m^3)$
$\Theta(2^m)$
$\Theta(m\,D_{1,m})$
$\Theta(m^2)$
Explanation. The matrix of the run costs is computed in $\Theta(m^2)$ and the recurrence $v(t)=\min_j\{v(j-1)+c_{j,t}\}$ in $\Theta(m^2)$: it is a shortest path. Recomputing every $c_{j,t}$ from scratch would cost $O(m^3)$.
Uncapacitated lot sizing (ULS) over $3$ periods: demands $d=(10,20,30)$, setup cost $sc_t=100$, zero variable cost, cost $hc_t=1$ per unit of stock at the end of a period. The cost of the run produced in $j$ for periods $j,\dots,t$ is $c_{j,t}=sc_j+vc_j\,D_{j,t}+\sum_{k=j}^{t-1}hc_k\,D_{k+1,t}$, with $D_{a,b}$ the demand of periods $a$ to $b$. What is $c_{1,3}$?
$130$
$160$
$180$
$150$
Explanation. $c_{1,3}=100+hc_1D_{2,3}+hc_2D_{3,3}=100+50+30=180$: the $20$ units of period $2$ are stocked one period, the $30$ of period $3$ two periods.
In uncapacitated lot sizing (ULS), $c_{j,t}$ is the cost of the run produced in period $j$ to cover the demands of periods $j,\dots,t$ (setup $sc_j$, variable cost $vc_j$, holding costs $hc_k$). How is $c_{j,t}$ obtained from $c_{j,t-1}$ in constant time?
Explanation. Extending the run to period $t$ adds $d_t$ units, produced in $j$ and stocked during periods $j,\dots,t-1$; the setup is already paid. Keeping the sum of the $hc_k$ updated, the cost matrix is computed in $\Theta(m^2)$.
In uncapacitated lot sizing (ULS) with $m$ periods, the cost matrix contains a value $c_{j,t}$ for every run produced in $j$ for periods $j,\dots,t$, with $1\le j\le t\le m$. How many values does it contain with $m=5$?
$15$
$25$
$10$
$32$
Explanation. The pairs $(j,t)$ with $j\le t$ are $\frac{m(m+1)}{2}=15$. $25$ also counts the pairs with $j>t$, which are not runs; $32=2^5$ counts the choices of setup periods.
Uncapacitated lot sizing (ULS) over $3$ periods: demands $d=(10,20,30)$, setup cost $sc_t=100$, zero variable cost, cost $hc_t=1$ per unit of stock at the end of a period. The run costs are $c_{1,1}=100$, $c_{1,2}=120$, $c_{1,3}=180$, $c_{2,2}=100$, $c_{2,3}=130$, $c_{3,3}=100$. With $v(0)=0$ and $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$, what is $v(3)$?
$220$
$230$
$300$
$180$
Explanation. $v(1)=100$, $v(2)=\min\{120,200\}=120$, $v(3)=\min\{180,\ 100+130,\ 120+100\}=180$: a single run in period $1$. The lot-for-lot plan costs $300$.
In the Wagner–Whitin algorithm for uncapacitated lot sizing, $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$ and $j^*(t)$ is the period attaining the minimum. How are the run periods rebuilt starting from $t=m$?
Record a run in every period $t$ with $v(t)<v(t-1)$
Record the runs in $j^*(1),j^*(2),\dots,j^*(m)$, forwards
Record a run in $j^*(t)$ and set $t\leftarrow j^*(t)-1$, until $t=0$
Record a run in $j^*(t)$ and set $t\leftarrow t-1$
Explanation. The last run is produced in $j^*(m)$ and covers periods $j^*(m)$ to $m$; the rest of the plan is the optimal solution of periods $1,\dots,j^*(m)-1$.
In the Wagner–Whitin algorithm for uncapacitated lot sizing, $v(t)$ is the optimal cost of periods $1,\dots,t$ with zero stock at the end of $t$. What does the index $j$ in the recurrence $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$ represent?
The quantity produced in period $t$
The period of the last run, which produces the demands of periods $j,\dots,t$
The period of the first run, which produces the demands of periods $1,\dots,j$
The number of runs of the plan
Explanation. By the zero-inventory ordering property, the stock is zero at the end of $j-1$, and the residual subproblem is the instance with periods $1,\dots,j-1$. The generated subproblems are therefore $t$.
In uncapacitated lot sizing (ULS) with $m$ periods, a solution with the zero-inventory ordering property produces only with zero incoming stock, so it is determined by the periods in which it produces (period $1$ always produces if $d_1>0$). How many such solutions are there with $m=6$?
$32$
$64$
$21$
$720$
Explanation. Every period $t\in\{2,\dots,6\}$ produces or not independently: $2^{m-1}=32$. Period $1$ must produce, because the initial stock is zero.
In uncapacitated lot sizing (ULS), in an optimal solution with the zero-inventory ordering property ($s_{t-1}x_t=0$ for every $t$), how much does a period $j$ with positive production produce?
Exactly the demand $d_j$ of its own period
The total demand $D_{1,m}$ of all periods
Any quantity, as long as the stock stays non-negative
Exactly the demands of periods $j,\dots,t$, where $t+1$ is the next production period (or $t=m$)
Explanation. With zero incoming stock, period $j$ must cover all the demand up to the next production period, which in turn starts with zero stock: the runs cover blocks of consecutive periods.
In uncapacitated lot sizing (ULS) $D_{j,t}=\sum_{k=j}^td_k$ is the demand of the periods from $j$ to $t$. With demands $d=(20,10,30,40,10)$, what is $D_{2,4}$?
$40$
$110$
$80$
$70$
Explanation. $D_{2,4}=d_2+d_3+d_4=10+30+40=80$. $70$ forgets $d_2$; $110$ is the total demand.
In uncapacitated lot sizing a feasible solution is a production vector $(x_1,\dots,x_m)$ with inventories $s_t=\sum_{j\le t}x_j-D_{1,t}\ge0$ for every $t$ and $s_m=0$. With $d=(20,10,30,40,10)$, which plan is feasible?
$(30,0,70,0,20)$
$(30,0,70,0,10)$
$(10,20,30,40,10)$
$(30,0,30,30,20)$
Explanation. Inventories of $(30,0,70,0,10)$: $10,0,40,0,0$. $(10,20,\dots)$ has $s_1=-10$; $(30,0,30,30,20)$ has $s_4=-10$; $(30,0,70,0,20)$ ends with inventory $10$.
In uncapacitated lot sizing the cost of the lot produced in period $j$ for the periods $j,\dots,t$ is $c_{j,t}=sc_j+vc_jD_{j,t}+\sum_{k=j}^{t-1}hc_kD_{k+1,t}$. With $d=(20,10,30,40,10)$, $sc_t=50$, $vc_t=0$ and $hc_t=1$, what is $c_{1,3}$?
$120$
$110$
$90$
$160$
Explanation. $50+hc_1D_{2,3}+hc_2D_{3,3}=50+40+30=120$: the demand of period $3$ stays in stock two periods, that of period $2$ one. $90$ counts the inventory only once.
In the cost of a lot of uncapacitated lot sizing, $c_{j,t}=sc_j+vc_jD_{j,t}+\sum_{k=j}^{t-1}hc_kD_{k+1,t}$, why is the holding term of period $k$ equal to $hc_kD_{k+1,t}$?
Because every unit stays in stock a single period
Because the demand of the periods from $j$ to $k$ is kept in stock
Because the holding cost is paid only in the setup period
At the end of period $k$ exactly the units meant for periods $k+1,\dots,t$ remain in stock
Explanation. The lot covers $D_{j,t}$; after period $k$ the demands up to $k$ have been delivered, so $D_{k+1,t}$ is in the warehouse, paying $hc_k$ per unit.
The Wagner-Whitin algorithm for uncapacitated lot sizing with $m$ periods computes $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$ for $t=1,\dots,m$. How many steps does it perform?
$\Theta(m)$: one term per period
$\Theta(m\,D_{1,m})$: pseudo-polynomial in the demand
$\Theta(m^2)$: one pair $(j,t)$ with $j\le t$ for every term of the minimum
$\Theta(2^m)$: one term for every set of setup periods
Explanation. The pairs $(j,t)$ are $m(m+1)/2$, and the same order holds for computing the cost matrix $c_{j,t}$. This is why the ULS is polynomial, unlike the CLS.
In the uncapacitated lot sizing model ($x_t$ production, $s_t$ inventory, $y_t$ setup of period $t$), which constraint imposes a setup in every period with positive production?
$x_t\le D_{t,m}\,y_t$, with $D_{t,m}$ the demand of the periods from $t$ to $m$
$s_{t-1}+x_t=d_t+s_t$
$y_t\le x_t$
$x_t\le d_t$
Explanation. If $y_t=0$ the constraint forces $x_t=0$; with $y_t=1$ one can produce up to the remaining demand, which is the natural big-$M$ without capacities.
Uncapacitated lot sizing with demands $d=(20,10,30,40,10)$, $sc_t=50$, $vc_t=0$, $hc_t=1$. What is the cost of the lot-for-lot plan, which produces in every period its own demand?
$110$
$50$
$360$
$250$
Explanation. Five setups of $50$ and no inventory: $250$. Producing everything in period $1$ would cost $50$ of setup plus $90+80+50+10=230$ of inventory.
Uncapacitated lot sizing with demands $d=(20,10,30,40,10)$: is the plan $(x_1,\dots,x_5)=(60,0,0,50,0)$ feasible? What are the inventories $s_t=\sum_{j\le t}x_j-D_{1,t}$?
Yes: $(40,30,0,50,0)$
No: $s_3<0$
Yes: $(40,30,0,10,0)$
No: the final inventory is positive
Explanation. $60-20=40$, $40-10=30$, $30-30=0$, $0+50-40=10$, $10-10=0$: all non-negative and final zero.
In uncapacitated lot sizing with $m=5$ periods, how many plans satisfy the zero-inventory property (production only with empty inventory), if every plan is identified by its setup periods and period $1$ always has a setup?
$120$
$16$
$32$
$5$
Explanation. Period $1$ must produce; each of the other $4$ periods produces or not: $2^4=16$. Every plan produces, in a setup period, the demand up to the next setup.
In uncapacitated lot sizing with $d=(20,10,30,40,10)$, $sc_t=50$, $vc_t=0$ and $hc_t=1$, the cost of the lot produced in period $j$ for the periods $j,\dots,t$ is $c_{j,t}=sc_j+\sum_{k=j}^{t-1}hc_kD_{k+1,t}$. What is $c_{3,4}$?
$90$
$70$
$120$
$50$
Explanation. $50+hc_3D_{4,4}=50+40=90$: the demand of period $4$ stays in stock one period.
The cost matrix of the Wagner-Whitin algorithm contains a value $c_{j,t}$ for every pair of periods $j\le t$. How many values does it have with $m=5$ periods?
$10$
$32$
$15$
$25$
Explanation. The pairs with $j\le t$ are $m(m+1)/2=15$; computing them for increasing $t$ every value is obtained from the previous one in constant time.
What does the zero-inventory ordering property (Wagner and Whitin) state for uncapacitated lot sizing (ULS), with productions $x_t$ and inventories $s_t$?
Every feasible solution has $x_t=d_t$
Some optimal solution has $s_{t-1}\,x_t=0$ for every $t$
Every optimal solution produces in every period
Some optimal solution has $s_t>0$ for every $t$
Explanation. A period produces only if it starts with an empty inventory: the production of a period covers the demand of consecutive periods.
In the Wagner–Whitin DP $v(t)=\min_{j\le t}\{v(j-1)+c_{j,t}\}$ for uncapacitated lot sizing with $m$ periods: how many steps, and what does the recurrence compute?
$\Theta(m)$; a minimum spanning tree
$\Theta(2^m)$; all production plans
$\Theta(m^3)$; a maximum flow
$\Theta(m^2)$; a shortest path in the network of the runs
Explanation. Nodes are $0,\dots,m$ and arc $(j-1,t)$ costs $c_{j,t}$: $v(t)$ is the length of a shortest path from $0$ to $t$.
In capacitated lot sizing (CLS) over $m$ periods, with zero initial and final inventory and $D_{t+1,m}$ the demand of periods $t+1$ to $m$, what is the DP state and where is the optimal value read?
The period $t$ of the last lot produced, as in the ULS; the optimal value is $v(m)$
The pair $(t,x)$ of the period and the production, with $x\le cap_t$; the optimal value is $v(m,cap_m)$
The pair $(t,k)$ of the period and the final inventory, with $k\le D_{t+1,m}$; the optimal value is $v(m,0)$
The pair $(t,k)$ of the period and the number of setups, with $k\le t$; the optimal value is $\min_k v(m,k)$
Explanation. With capacities the zero-inventory ordering property fails, so the state must contain the inventory; at the end of the horizon the inventory is zero.
In the DP of capacitated lot sizing (CLS), $v(t,k)$ is the minimum cost of periods $1,\dots,t$ ending with inventory $k$; the initial inventory is zero. What is $v(0,k)$ for $k>0$?
$k$: one unit of cost per unit of inventory
$+\infty$: these states are not reachable
$0$: no cost has been paid yet
$-\infty$: these states are not reachable
Explanation. The value $+\infty$ marks the states that cannot be reached; only $v(0,0)=0$.
In capacitated lot sizing (CLS) over $m$ periods, with total demand $D$ and maximum capacity $C$, which statement on the complexity is correct?
The DP executes $O(mDC)$ steps; with constant capacity it is polynomial, with general capacities NP-hard
The DP executes $O(mDC)$ steps; with constant capacity it is strongly NP-hard
The Wagner-Whitin DP on lots also solves the CLS in $\Theta(m^2)$ steps
The DP executes $O(m^2)$ steps; the CLS is polynomial for any capacity
Explanation. With capacities the state needs the inventory, and the number of states depends on the total demand $D$; with constant capacity a weaker property holds that makes the problem polynomial.
In the DP for capacitated lot sizing (CLS), the state $(t,k)$ is period $t$ with final stock $k$, and only $k\le D_{t+1,m}$ (demand of periods $t+1$ to $m$) is considered. Why?
Because the states with larger stock have zero cost
A stock larger than the residual demand would stay unused and violate the zero final stock
Because the capacity of period $t$ is at most $D_{t+1,m}$
Because the stock cannot exceed the demand of period $t$
Explanation. The stock at the end of $t$ serves only later periods and must be zero at the end: beyond $D_{t+1,m}$ it cannot be consumed, so those states lead to no feasible solution.
Capacitated lot sizing (CLS) over $2$ periods: demands $d=(2,3)$, capacity $cap_t=4$, setup $sc_t=10$, zero variable cost, holding cost $hc_1=1$ per unit at the end of period $1$; zero initial and final stock. What is the optimal cost?
$20$
$22$
$12$
$10$
Explanation. The plan $(2,3)$ costs $20$; $(4,1)$ costs $10+2+10=22$; a single setup ($5$ units in period $1$) exceeds the capacity $4$, so $12$ is infeasible.
In the DP for capacitated lot sizing, the state $(t,k)$ has stock $k$ at the end of period $t$. From which states $(t-1,k')$ can $(t,k)$ be reached?
From all states $(t-1,k')$ with $k'\le k$
Only from state $(t-1,0)$, by the zero-inventory property
From those with $k'=k+d_t$
From those for which the production $x=k+d_t-k'$ satisfies $0\le x\le cap_t$
Explanation. The balance $k'+x=d_t+k$ fixes the production of period $t$, which must be non-negative and respect the capacity. With capacities the zero-inventory property no longer holds.
In the DP for capacitated lot sizing over $m$ periods, with total demand $D$ and largest capacity $C$, why is the number of steps $O(mDC)$?
There are $2^m$ setup choices, each evaluated in $O(DC)$
There are $D\cdot C$ states and $m$ transitions per state
There are at most $m(D+1)$ states $(t,k)$, and each has at most $C+1$ transitions, one per production quantity
There are $m$ states, each needing $DC$ comparisons
Explanation. The final stock of a period ranges from $0$ to $D$, and the production of the period from $0$ to $C$. The time is pseudo-polynomial: it contains the numbers $D$ and $C$.
Why does the Wagner–Whitin algorithm, which only chooses the periods of the runs, not solve capacitated lot sizing (CLS)?
Because the CLS has a free final stock
With capacities an optimal plan producing only at zero incoming stock may not exist
Because in the CLS the setup costs are zero
Because in the CLS demands can be negative
Explanation. If the demand of a period exceeds its capacity, an earlier period must produce in advance even with stock on hand: the zero-inventory ordering property fails, and states with the stock are needed.
In the DP for capacitated lot sizing, the transition from $(t-1,k')$ to $(t,k)$ produces $x=k+d_t-k'$ units in period $t$. Which costs are added?
$sc_t$ if $x>0$, plus $vc_t\,x$, plus $hc_t\,k$ for the final stock of period $t$
Always $sc_t$, plus $vc_t\,x$
$sc_t$ if $x>0$, plus $hc_t\,k'$ for the initial stock
Only $hc_t\,k$, because the setup is paid once
Explanation. The setup is paid only if we produce; the stock left at the end of the period pays $hc_t$ per unit, as in the objective function of the model.
In the DP for capacitated lot sizing, the capacity of period $t$ is $cap_t=3$. From how many states $(t-1,k')$ can a state $(t,k)$ be reached at most?
$3$, one for every unit of capacity
$2$: produce or not
$k+1$, one for every smaller stock
$4$, one for every production $x\in\{0,1,2,3\}$
Explanation. Given $k$ and $d_t$, the previous stock is $k'=k+d_t-x$: one for every allowed production, as long as $k'\ge 0$ and within the state range.
Capacitated lot sizing over $2$ periods with demands $d=(5,1)$, capacity $cap_t=4$ and zero initial stock. What does the DP give on the states $(1,k)$, stock $k$ at the end of period $1$?
$v(1,k)=0$ for every $k$, because period $1$ does not produce
$v(1,1)=sc_1+hc_1$, with one unit in stock
$v(1,k)=+\infty$ for every $k$: the demand of period $1$ exceeds its capacity
$v(1,0)=sc_1$, the others $+\infty$
Explanation. Without initial stock period $1$ must produce at least $5$ units, but the capacity is $4$: no state of period $1$ is reachable, and the instance has no solution.
Capacitated lot sizing (CLS) is NP-hard in general, and its DP is pseudo-polynomial. What happens when the capacity is the same in all periods?
The Wagner–Whitin algorithm suffices without changes
The problem is solved in polynomial time
The problem stays strongly NP-hard
The DP becomes exponential in $m$
Explanation. With constant capacity polynomial algorithms exist; with general capacities the CLS is NP-hard. In both cases the zero-inventory ordering property may fail.
Capacitated lot sizing with demands $d=(2,1,3,4,1)$ and capacities $cap_t=4$. The plan $(3,0,4,4,0)$ is feasible; what are the inventories $s_t=\sum_{j\le t}x_j-D_{1,t}$ at the end of the periods?
$(1,0,0,1,0)$
$(1,0,1,1,0)$
$(1,1,1,1,0)$
$(3,0,4,4,0)$
Explanation. $3-2=1$, $1-1=0$, $0+4-3=1$, $1+4-4=1$, $1+0-1=0$. Period $4$ produces while there is inventory: with capacities the zero-inventory property fails.
The DP for capacitated lot sizing uses the state $(t,k)$: $v(t,k)$ is the optimal cost of periods $1,\dots,t$ with inventory $k$ at the end of period $t$. Why is it enough to consider $k\le D_{t+1,m}$?
The inventory must be empty at the end of the horizon, so it never exceeds the demand of the following periods
Because the capacity is at most $D_{t+1,m}$
Because the inventory is always zero
Because $k$ must be a multiple of the capacity
Explanation. Units beyond $D_{t+1,m}$ could never be delivered before the end: a plan with empty final inventory does not produce them.
In the DP for capacitated lot sizing, $v(t,k)=\min\{v(t-1,k+d_t-x)+f_t(x):x\in X_t(k)\}+hc_tk$, where $x$ is the production of period $t$. Why is the state of the previous period $k+d_t-x$?
Because one always produces $d_t$
Because the inventory of the previous period is always $k$
Because the demand is paid in the next period
Initial inventory of period $t$ plus production minus demand must give the final inventory $k$
Explanation. From the balance $s_{t-1}+x=d_t+k$ one gets $s_{t-1}=k+d_t-x$. The allowed productions are $X_t(k)=\{0,\dots,\min\{cap_t,k+d_t\}\}$.
The DP for capacitated lot sizing performs $O(m\,D\,C)$ steps, with $m$ periods, $D$ total demand and $C$ maximum capacity. How is the algorithm classified?
Exponential in $m$
Linear in the instance size
Pseudo-polynomial: it is polynomial in the numerical values $D$ and $C$, not in their length in bits
Polynomial in the instance size
Explanation. The CLS with general capacities is NP-hard, so no polynomial algorithm is expected; the DP is exact and fast when $D$ and $C$ are small.
Capacitated lot sizing is NP-hard with general capacities, but becomes polynomial with constant capacity $cap_t=C$. Which property of optimal plans replaces the zero-inventory ordering property?
Every period produces exactly its own demand
Between two consecutive periods with empty inventory at most one period produces a quantity strictly between $0$ and $C$; the others produce $0$ or $C$
One produces only with empty inventory
Every period produces exactly $C$
Explanation. With constant capacity «full» and «empty» periods can be swapped without losing feasibility, and a single fractional period per block remains. With different capacities the property fails.
Capacitated lot sizing with demands $d=(2,1,3,4,1)$ and capacity $cap_t=4$ in every period. Which plan is infeasible?
$(4,0,2,4,1)$
$(6,0,0,5,0)$
$(3,0,4,4,0)$
$(2,1,3,4,1)$
Explanation. $(6,0,0,5,0)$ exceeds the capacity in periods $1$ and $4$. The others have non-negative inventories, zero final inventory and productions at most $4$.
The Wagner-Whitin DP for uncapacitated lot sizing enumerates the lots (periods from $j$ to $t$ covered by a single production). Why can it not be used for capacitated lot sizing?
It relies on the zero-inventory property, which fails with capacities: a lot may not fit in the capacity of its period
Because with capacities the setup costs are zero
Because the CLS has a single period
It can be used without changes
Explanation. In the optimal plan $(3,0,4,4,0)$ with $cap_t=4$ period $4$ produces with positive inventory; this is why the CLS DP uses the state (period, inventory).
In the DP for capacitated lot sizing the state $(t,k)$ has $k\in\{0,\dots,D_{t+1,m}\}$. With demands $d=(2,1,3,4,1)$, how many states are there for $t=1,\dots,5$ overall?
$55$
$25$
$11$
$28$
Explanation. $D_{2,5}=9$, $D_{3,5}=8$, $D_{4,5}=5$, $D_{5,5}=1$, $D_{6,5}=0$: $10+9+6+2+1=28$ states.
In the DP for capacitated lot sizing every state $(t,k)$ tries the productions $x\in\{0,\dots,\min\{cap_t,k+d_t\}\}$. Where does the bound $O(m\,D\,C)$ come from, with $D$ total demand and $C$ maximum capacity?
From $m^2$ pairs of periods
From $D\cdot C$ pairs of periods
At most $D+1$ inventories for each of the $m$ periods, and at most $C+1$ productions per state
From $2^m$ setup plans
Explanation. States $O(mD)$ times attempts $O(C)$: pseudo-polynomial in the values $D$ and $C$.
Capacitated lot sizing with constant capacity $C=4$ and demands $d=(2,1,3,4,1)$: the optimal plan $(3,0,4,4,0)$ has inventories $(1,0,1,1,0)$. How does it satisfy the property of constant-capacity plans?
Every period produces its own demand
Between two periods with empty inventory, in periods $1$–$2$ only period $1$ produces between $0$ and $4$, and in periods $3$–$5$ one produces $0$ or $4$
Every period produces exactly $4$
One produces only with empty inventory
Explanation. The property allows at most one «fractional» production between two empty-inventory instants: this is what makes the constant-capacity case polynomial.
In the DP for capacitated lot sizing (CLS) the state is $(t,k)$, with $k$ the inventory at the end of period $t$. Where is the optimal value read, with $m$ periods?
In $v(1,0)$
In $v(m,0)$
In $v(0,m)$
In $\max_k v(m,k)$
Explanation. At the end of the horizon the inventory is zero: the optimal value is that of state $(m,0)$.
What is known about the complexity of single-item capacitated lot sizing?
It is always polynomial
It is NP-hard even without capacities
With constant capacity it is NP-hard
With constant capacity it is polynomial; with general capacities it is NP-hard
Explanation. With constant capacity a weaker property holds and the problem is polynomial; in general the DP on the states $(t,k)$ is only pseudo-polynomial.
Coin change (CCP): with denominations $w=(3,5)$ a change of exactly $c=7$ must be given with the minimum number of coins. What is $v(7)$ with the recurrence $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, $v(0)=0$ and minimum over an empty set equal to $+\infty$?
$+\infty$
$0$
$2$
$3$
Explanation. $v(1)=v(2)=+\infty$, $v(4)=1+v(1)=+\infty$, hence $v(7)=\min\{1+v(4),1+v(2)\}=+\infty$: the amount $7$ cannot be returned. With the value $0$ the algorithm would claim that no coin is needed.
In coin change (CCP) the denominations have values $w_j$ and the change is $c$; in the unbounded knapsack (UKP) the types have weights $w_j$, profits $p_j$ and the capacity is $c$; in both copies are unlimited. What is the difference?
The CCP requires sum at most $c$ and minimizes the coins; the UKP requires weight exactly $c$ and maximizes the profit
The CCP requires sum exactly $c$ and maximizes the coins; the UKP requires weight at most $c$ and minimizes the weight
The CCP allows at most one coin per denomination; the UKP allows unlimited copies of every type
The CCP requires sum exactly $c$ and minimizes the coins; the UKP requires weight at most $c$ and maximizes the profit
Explanation. The two recurrences look alike, but the CCP requires equality (hence $+\infty$ for impossible amounts) and has a minimization objective.
In coin change (CCP) with $n$ denominations and change $c$, the DP computes $v(k)$, the minimum number of coins for change $k$, for $k=0,\dots,c$. How many steps does it execute?
$\Theta(n^c)$
$\Theta(c\log n)$, polynomial
$\Theta(nc)$, pseudo-polynomial
$\Theta(n+c)$
Explanation. For each of the $c+1$ values $k$ the $n$ denominations are tried: $\Theta(nc)$, polynomial in the value of $c$ and not in its size.
Coin change (CCP) with denominations $w=(4,6)$, in unlimited supply, and amount $c=9$. What is the minimum number of coins?
No solution: even denominations cannot give an odd amount
$2$
$3$
$1$
Explanation. Every combination of $4$ and $6$ is even, so $9$ cannot be obtained and the instance has no feasible solution: the DP gives $v(9)=+\infty$.
Coin change (CCP) with denominations $w=(1,3,4)$ and amount $c=6$. Denomination $j$ is used at most $\lfloor c/w_j\rfloor$ times. How many vectors $(x_1,x_2,x_3)$ with $0\le x_j\le\lfloor c/w_j\rfloor$ are there, before checking the sum?
$12$
$27$
$64$
$42$
Explanation. $(6+1)(2+1)(1+1)=7\cdot3\cdot2=42$; only those summing to exactly $6$ are feasible.
Coin change (CCP) with denominations $w=(1,3,4)$ and amount $c=6$. With $v(0)=0$ and $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, what is $v(6)$?
$6$
$1$
$2$
$3$
Explanation. $6=3+3$ uses $2$ coins. The greedy that always takes the largest denomination uses $4+1+1$, i.e., $3$ coins: with these denominations it is not optimal.
In the DP for coin change, $v(k)$ is the minimum number of coins for amount $k$. Which value is given to $v(k)$ when no denomination $w_j\le k$ leaves an obtainable amount $k-w_j$?
$k$: coins of $1$ are used
$+\infty$: amount $k$ cannot be paid
$0$: no coin is needed
$-\infty$: the subproblem is infeasible
Explanation. In a minimization problem a subproblem without solutions is worth $+\infty$, so it is never chosen by the minimum. $v(0)=0$ is the only case with zero coins.
In the DP for coin change, $s(k)$ is the denomination attaining the minimum in $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$. How are the coins of an optimal solution for amount $c$ rebuilt?
Starting from $k=c$: take a coin $w_{s(k)}$ and set $k\leftarrow k-w_{s(k)}$, until $k=0$
Take $v(c)$ coins of denomination $s(c)$
Starting from $k=0$: take $w_{s(k)}$ and set $k\leftarrow k+w_{s(k)}$
Take the coins by decreasing denomination, as the greedy
Explanation. Every step of the recurrence removes one coin from the amount; the denominations are read backwards from the final state $c$ and can repeat.
In the recursion tree of the DP for coin change, every node is a call $v(k)$. How many children does node $v(k)$ have?
Two: use or not use denomination $1$
$k$, one per smaller amount
Only one, with the largest denomination that fits
One per denomination $w_j\le k$, with the call $v(k-w_j)$
Explanation. The recurrence tries as first coin every denomination fitting the amount, and each choice leaves the subproblem $v(k-w_j)$. The same amount reappears in different branches: overlapping subproblems.
Coin change (CCP) with denominations $w=(2,5)$. With $v(0)=0$, $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$ and $v(k)=+\infty$ for unobtainable amounts, what is $v(8)$?
$2$
$3$
$4$
$+\infty$
Explanation. $v=(0,+\infty,1,+\infty,2,1,3,2,4)$ for $k=0,\dots,8$: $8=2+2+2+2$, while $8-5=3$ is not obtainable. The greedy would start from $5$ and get stuck.
The coin change DP, $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, looks like the first DP of the unbounded knapsack, $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$. What are the two differences?
None: with $p_j=1$ the two recurrences coincide
Minimum instead of maximum, and $+\infty$ for unobtainable amounts because the sum must be exact
Bounded copies instead of unlimited, and a two-dimensional table
Maximum instead of minimum, and $0$ for unobtainable amounts
Explanation. The CCP minimizes the number of coins and requires sum exactly $c$; the knapsack maximizes profit and accepts unused capacity, so its subproblems are worth at least $0$.
In coin change (CCP: denominations $w_1,\dots,w_n$, change $c$, the number of coins is minimized) a solution is a vector $(x_1,\dots,x_n)$ of coins per denomination. Which condition makes it feasible?
$\sum_jw_jx_j\ge c$
$\sum_jw_jx_j=c$ with $x_j\in\Z_{\ge0}$
$\sum_jw_jx_j\le c$ with $x_j\in\{0,1\}$
$\sum_jx_j=c$
Explanation. The change must be given exactly; every denomination can be used several times, with $x_j\le\lfloor c/w_j\rfloor$. With $\le$ the problem would allow not giving the change.
The DP for coin change computes the minimum number of coins for every change $0,1,\dots,c$, trying the $n$ denominations for each. How many steps does it perform and why is it not polynomial?
$\Theta(nc)$, pseudo-polynomial: it depends on the value $c$, not on its length in bits
$\Theta(n\log c)$, polynomial
$\Theta(2^n)$, exponential in the number of denominations
$\Theta(c^2)$, quadratic in the change
Explanation. There are $c+1$ changes and for each one $n$ denominations are tried. Doubling $c$ doubles the steps, but adds a single bit to the instance.
Coin change with denominations $w=(1,3,4)$ and change $c=6$: the number of coins is minimized. Which vector $(x_1,x_2,x_3)$ is optimal, and how many coins does the greedy choice «largest denomination first» use?
$(6,0,0)$ with $6$ coins; the greedy uses $3$
$(0,2,0)$ with $2$ coins; the greedy uses $3$ ($4+1+1$)
$(2,0,1)$ with $3$ coins; the greedy uses $3$
$(0,2,0)$ with $2$ coins; the greedy uses $2$
Explanation. $3+3=6$ with two coins. The greedy takes $4$ and then two coins of $1$: with these denominations it is not optimal, hence the DP.
In coin change with denominations $w=(1,3,4)$ and change $c=6$, every component of a feasible solution satisfies $x_j\le\lfloor c/w_j\rfloor$. What are the bounds?
$x_1\le6$, $x_2\le2$, $x_3\le1$
$x_j\le1$ for every $j$
$x_1\le6$, $x_2\le3$, $x_3\le2$
$x_1+x_2+x_3\le6$, nothing else
Explanation. $\lfloor6/1\rfloor=6$, $\lfloor6/3\rfloor=2$, $\lfloor6/4\rfloor=1$: the solutions are finite, but their number grows quickly with $c$ and $n$.
In coin change (CCP) with denominations $w_1,\dots,w_n$ and amount $c$: what does $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$ with $v(0)=0$ compute, and in how many steps?
The minimum number of coins; $\Theta(c\log c)$
The maximum value with $k$ coins; $\Theta(n^2)$
The minimum number of coins for amount $k$; $\Theta(nc)$
The number of ways to form $k$; $\Theta(nc)$
Explanation. Each denomination is tried for the first coin; for each of the $c+1$ amounts $n$ denominations are examined.
In rod cutting (RCP) a rod of integer length $n$ is cut at integer positions and the pieces are sold at given prices. How many cutting patterns does a rod of length $n=5$ have?
$5$
$16$
$32$
$7$
Explanation. Each of the $n-1=4$ inner positions is cut or not: $2^{n-1}=16$ patterns. The patterns are more than the solution vectors, because different patterns can give the same pieces.
In rod cutting (RCP) a rod of length $n$ is cut into integer pieces and the piece of length $j$ is worth $p_j$ (the instance lists $p_1,\dots,p_n$). The DP $v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}$ executes $\Theta(n^2)$ steps. Why is this polynomial time, while the $\Theta(nc)$ of the KP DP is not?
The input contains the $n$ prices, hence $n$ grows with the instance size
The prices $p_j$ are integer, hence the table has integer values
The length $n$ is written in binary with $\log n$ digits
It is not: $\Theta(n^2)$ is pseudo-polynomial time too
Explanation. In the KP the capacity $c$ is a number written with $\log c$ digits; in rod cutting the instance lists $n$ profits, so $n$ is already a measure of the size.
In rod cutting (RCP), $v(\ell)$ is the maximum revenue from a rod of length $\ell$, with the piece of length $j$ sold at $p_j$, and $v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}$. What is the base case $v(0)=0$ for?
To forbid the rod without cuts, which is not a feasible pattern
To guarantee that the rod is cut at least once
To nothing: the recurrence never reads cell $v(0)$
To the term $p_\ell+v(0)$, i.e., selling the whole rod without cuts
Explanation. The term $p_\ell+v(0)$ corresponds to selling the whole rod without cuts; without the base case the recursion would not stop.
In rod cutting (RCP) the recurrence is $v(0)=0$ and $v(\ell)=\max_{1\le j\le\ell}\{p_j+v(\ell-j)\}$. Without a lookup table, the top-down recursion for $v(\ell)$ makes one call per $v(\ell-j)$, $j=1,\dots,\ell$. How many calls in total, including the first, are needed for $v(4)$?
$16$
$5$
$10$
$24$
Explanation. With $C(\ell)$ the number of calls, $C(0)=1$ and $C(\ell)=1+\sum_{i<\ell}C(i)$: $C=1,2,4,8,16$, i.e., $2^\ell$. With the lookup table $5$ values suffice, $v(0),\dots,v(4)$.
Rod cutting (RCP): rod of length $4$, piece prices $p=(1,5,8,9)$ for lengths $1,2,3,4$. With $v(0)=0$ and $v(\ell)=\max_{1\le j\le\ell}\{p_j+v(\ell-j)\}$, what is $v(4)$?
$9$
$11$
$20$
$10$
Explanation. $v(1)=1$, $v(2)=5$, $v(3)=8$, $v(4)=\max\{1+8,5+5,8+1,9+0\}=10$: two pieces of length $2$. Selling the whole rod gives only $9$.
In the first DP for rod cutting, $s(\ell)$ is the length of the first piece attaining the maximum in $v(\ell)$. How are the pieces of an optimal cut of the rod of length $n$ rebuilt?
Starting from $\ell=1$ and adding pieces until the sum is $n$
Read $v(n)$ and divide by the largest price
Starting from $\ell=n$: cut a piece $s(\ell)$ and set $\ell\leftarrow\ell-s(\ell)$, until $\ell=0$
Cut $n/s(n)$ pieces of length $s(n)$
Explanation. Every step removes the first piece chosen by the recurrence and moves to the residual rod; the lengths are read backwards and may repeat.
In the second DP for rod cutting, $v(j,\ell)$ is the largest revenue from a rod of length $\ell$ using pieces of length at most $j$. Why is the base case $v(0,\ell)=-\infty$ for $\ell>0$?
Because the table starts at $\ell=1$
With no piece length available a rod of positive length cannot be divided: no solution
Because prices can be negative
Because the whole rod cannot be sold without cuts
Explanation. The whole rod must be divided into pieces; with $j=0$ there is no piece, and $-\infty$ excludes the case from the maximum. Instead $v(j,0)=0$.
In the second DP for rod cutting, $v(j,\ell)=\max\{v(j-1,\ell),\ p_j+v(j,\ell-j)\}$ for $j\le\ell$. What does the term $p_j+v(j,\ell-j)$ represent?
Cutting a piece of length $j$, with more pieces of the same length still allowed
Not using pieces of length $j$
Cutting a piece of length $j$ and moving to smaller lengths
Selling the whole rod of length $\ell$
Explanation. The term stays in row $j$, so length $j$ can still be used; $v(j-1,\ell)$ excludes length $j$ instead. It is the same structure as the unbounded knapsack.
Rod cutting with prices $p=(1,5,8,9)$ for lengths $1,2,3,4$. In the second DP, $v(j,\ell)$ is the largest revenue from a rod of length $\ell$ with pieces of length at most $j$. What is $v(1,4)$?
$-\infty$
$1$
$10$
$4$
Explanation. With pieces of length $1$ only the rod is divided into $4$ pieces of $1$: revenue $4$. $10=v(4,4)$ also uses pieces of length $2$.
In rod cutting (RCP) a rod of length $n$ has $2^{n-1}$ cutting schemes, because at every integer position we cut or not. If instead the order of the pieces does not matter (only their lengths count), how many distinct cuts does a rod of length $5$ have?
$32$
$7$
$16$
$5$
Explanation. They are the partitions of the integer $5$: $5$, $4+1$, $3+2$, $3+1+1$, $2+2+1$, $2+1+1+1$, $1+1+1+1+1$. The revenue depends only on the lengths, so many of the $16$ schemes are equivalent.
Rod cutting (rod of length $n$, piece of length $j$ sold at $p_j$) can be seen as an unbounded knapsack. With which item types and which constraint?
Type $j$ with weight $j$ and profit $p_j$, unlimited copies, total weight exactly $n$
Type $j$ with weight $p_j$ and profit $j$, at most one copy, capacity $n$
A single type of weight $1$ and profit $\max_j p_j$, capacity $n$
Type $j$ with weight $j$ and profit $p_j$, at most one copy per type
Explanation. Every piece is a copy of the type of its length, and the pieces must cover the rod. With a piece of length $1$ and non-negative prices, the «weight at most $n$» version has the same optimum.
In rod cutting (RCP: rod of integer length $n$, a piece of length $\ell$ is worth $p_\ell$) a solution is encoded by $(x_1,\dots,x_n)$, $x_\ell$ = number of pieces of length $\ell$. Which cutting schemes have the same vector?
None: every scheme has a different vector
Those with the same number of cuts
Those with the same longest piece
Those producing the same pieces in a different order, and they have the same profit
Explanation. The vector counts the pieces by length, not the order of the cuts: for $n=4$ the cuts $1+3$ and $3+1$ give the same vector $(1,0,1,0)$. This is why the $2^{n-1}$ schemes outnumber the distinct vectors.
A rod of length $n=4$ is cut into integer pieces; the pieces are worth $p=(1,5,8,9)$ for length $\ell=1,2,3,4$. How many cutting schemes are there (counting the order) and what is the maximum profit?
$5$ schemes, maximum profit $10$
$16$ schemes, maximum profit $13$
$8$ schemes, maximum profit $10$
$8$ schemes, maximum profit $9$
Explanation. Each of the $n-1=3$ positions is cut or not: $2^3=8$. The maximum is $5+5=10$ with two pieces of length $2$; the whole rod is worth $9$, $1+8=9$.
The DP for rod cutting computes $v(k)=\max_{1\le\ell\le k}\{p_\ell+v(k-\ell)\}$ for $k=1,\dots,n$. How many steps does it perform, and why is it not merely pseudo-polynomial like the knapsack DP?
$\Theta(n^2)$, but pseudo-polynomial since it depends on $n$
$\Theta(n^2)$; the input contains $n$ prices, so it is polynomial in the size
$\Theta(2^n)$, like the enumeration of the schemes
$\Theta(n)$, one step per length
Explanation. For every $k$, $k$ first pieces are tried: $\sum_kk=\Theta(n^2)$. Here $n$ is also the number of data (the prices $p_1,\dots,p_n$), so $\Theta(n^2)$ is polynomial in the instance size.
Rod cutting has two DP algorithms: the first chooses the first piece cut, the second treats the lengths $\ell=1,\dots,n$ as item types of an unbounded knapsack of capacity $n$. How many steps does the second perform?
$\Theta(n^2)$, as the first: $n$ types times $n+1$ capacities
$\Theta(n)$
$\Theta(n^3)$
$\Theta(2^n)$
Explanation. The unbounded knapsack DP performs $\Theta(\text{types}\cdot\text{capacity})$ steps, here $\Theta(n\cdot n)$. The two algorithms have the same order of growth.
A rod of integer length $n=5$ is cut into pieces of integer length, deciding for each of the $n-1$ intermediate positions whether to cut. How many cutting schemes are there, counting the order of the pieces?
$7$
$120$
$16$
$32$
Explanation. $2^{n-1}=2^4=16$. The distinct vectors of pieces (partitions of the number $5$) are only $7$, since the order does not count.
Rod cutting with $n=5$ and prices $p=(1,5,8,9,10)$ for the lengths $1,\dots,5$. The cuts produce the pieces $2,1,2$. What is the vector $(x_1,\dots,x_5)$ and what is the profit?
$(0,1,0,0,1)$, profit $15$
$(1,2,0,0,0)$, profit $11$
$(2,1,0,0,0)$, profit $7$
$(1,2,0,0,0)$, profit $3$
Explanation. One piece of length $1$ and two of length $2$: $1\cdot1+2\cdot2=5$ and profit $1+2\cdot5=11$.
The second DP for rod cutting treats the lengths $\ell=1,\dots,n$ as item types (weight $\ell$, profit $p_\ell$) of an unbounded knapsack of capacity $n$. Why unbounded and not 0/1?
Because every length is used at most once
Because the prices are integer
Several pieces of the same length can be cut
Because the rod may be longer than $n$
Explanation. For instance $n=4$ with two pieces of length $2$: two copies of the same type. With $n$ types and capacity $n$ the number of steps is $\Theta(n^2)$.
In the second DP for rod cutting (unbounded knapsack with types $\ell=1,\dots,n$ and capacity $n$) one cell is updated for every pair (type, capacity $1,\dots,n$). How many pairs are there for $n=4$?
$8$
$16$
$10$
$20$
Explanation. $4$ types times $4$ positive capacities: $16$ updates, $\Theta(n^2)$ as the first DP.
In rod cutting (RCP) with a rod of length $n$ and profits $p_1,\dots,p_n$, the DP $v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}$ executes $\Theta(n^2)$ steps. Why is this time polynomial?
Because the profits are integer
Because $n$ is written with $\log n$ bits
Because the recurrence has one base case
The input contains $n$ profits: $n$ is also the number of data
Explanation. Unlike $c$ in the knapsack, $n$ counts the input values: $\Theta(n^2)$ is polynomial in its size.
In the DP for rod cutting, $v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}$: which hypothesis on the pieces allows the same recurrence for the residual rod $\ell-j$?
Profits grow with the length
The rod is cut into two pieces
Each length can be cut any number of times
Each length at most once
Explanation. The piece of length $j$ stays available: the residual rod is the same problem with length $\ell-j$.
Explanation. It is the base case: without a rod there is nothing to sell.
Generated questions (25)
Each generator builds a new instance, with different numbers, at every start: a few examples here.
2. DP for the 0/1 knapsack problem (2)
Example 1 · dp-g-kp-dp-cella · level facile · notes
0-1 knapsack problem (KP) with items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 4 & 3 & 6 & 4\\ w_j & 6 & 3 & 2 & 4\end{array}$ and capacity $c=9$; $v(j,k)$ is the largest profit with items $1,\dots,j$ and capacity $k$, with $v(0,k)=0$. With the recursion $v(j,k)=\max\{v(j-1,k),\,p_j+v(j-1,k-w_j)\}$ (the second term only if $w_j\le k$), what is $v(3,7)$?
$13$
$4$
$9$
$18$
Explanation. $v(3,7)$ is the largest profit with the items $\{1,2,3\}$ and capacity $7$: it is $9$. Each item is used at most once (with repetitions one would get $18$, the value of the unbounded knapsack).
Example 2 · dp-g-kp-dp-cella · level facile · notes
0-1 knapsack problem (KP) with items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 11 & 3 & 11 & 9\\ w_j & 3 & 3 & 3 & 5\end{array}$ and capacity $c=11$; $v(j,k)$ is the largest profit with items $1,\dots,j$ and capacity $k$, with $v(0,k)=0$. With the recursion $v(j,k)=\max\{v(j-1,k),\,p_j+v(j-1,k-w_j)\}$ (the second term only if $w_j\le k$), what is $v(3,10)$?
$25$
$14$
$34$
$33$
Explanation. $v(3,10)$ is the largest profit with the items $\{1,2,3\}$ and capacity $10$: it is $25$. Each item is used at most once (with repetitions one would get $33$, the value of the unbounded knapsack).
Example 1 · dp-g-kp-dp-completa · level complessa · notes
0-1 knapsack problem (KP: choose a subset of items of maximum profit with total weight at most $c$) with capacity $c=11$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 10 & 14 & 13 & 11\\ w_j & 4 & 5 & 2 & 5\end{array}$. The DP table, $v(j,k)$ = largest profit with items $1,\dots,j$ and capacity $k$, is computed and an optimal solution is reconstructed going back from $(4,11)$. What are the optimal value and the optimal set $\tilde S$?
$v(4,11)=27$, $\tilde S=\{2,3\}$
$v(4,11)=25$, $\tilde S=\{2,4\}$
$v(4,11)=34$, $\tilde S=\{1,3,4\}$
$v(4,11)=37$, $\tilde S=\{1,2,3\}$
Explanation. The table gives $v(4,11)=37$; going back from $(4,11)$ (item $j$ is selected if $v(j,k)\ne v(j-1,k)$) gives $\tilde S=\{1,2,3\}$. The greedy by efficiency only gives $37$.
Example 2 · dp-g-kp-dp-completa · level complessa · notes
0-1 knapsack problem (KP: choose a subset of items of maximum profit with total weight at most $c$) with capacity $c=11$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 13 & 4 & 14 & 11\\ w_j & 3 & 3 & 3 & 5\end{array}$. The DP table, $v(j,k)$ = largest profit with items $1,\dots,j$ and capacity $k$, is computed and an optimal solution is reconstructed going back from $(4,11)$. What are the optimal value and the optimal set $\tilde S$?
$v(4,11)=38$, $\tilde S=\{1,3,4\}$
$v(4,11)=29$, $\tilde S=\{2,3,4\}$
$v(4,11)=31$, $\tilde S=\{1,2,3\}$
$v(4,11)=28$, $\tilde S=\{1,2,4\}$
Explanation. The table gives $v(4,11)=38$; going back from $(4,11)$ (item $j$ is selected if $v(j,k)\ne v(j-1,k)$) gives $\tilde S=\{1,3,4\}$. The greedy by efficiency only gives $38$.
Unbounded knapsack (UKP): $n=3$ item types, each available in unlimited copies, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 10 & 18 & 21\\ w_j & 3 & 5 & 7\end{array}$, capacity $c=12$. $v(k)$ is the largest profit with capacity $k$: $v(0)=0$ and $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$ (equal to $0$ if no type fits). What is $v(12)$?
$36$
$40$
$39$
$38$
Explanation. The table gives $v(12)=40$. Each type can be used several times: the value $39$ is that of the 0/1 KP, and the greedy by efficiency with repetitions ($36$) is not optimal in general.
Unbounded knapsack (UKP): $n=3$ item types, each available in unlimited copies, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 10 & 12 & 7\\ w_j & 4 & 6 & 3\end{array}$, capacity $c=14$. $v(k)$ is the largest profit with capacity $k$: $v(0)=0$ and $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$ (equal to $0$ if no type fits). What is $v(14)$?
$29$
$31$
$34$
$30$
Explanation. The table gives $v(14)=34$. Each type can be used several times: the value $29$ is that of the 0/1 KP, and the greedy by efficiency with repetitions ($30$) is not optimal in general.
Unbounded knapsack (UKP): $n=3$ item types, each in unlimited copies, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 11 & 9 & 13\\ w_j & 4 & 6 & 5\end{array}$, capacity $c=10$; $x_j$ is the number of copies of type $j$. What is the optimal value, and with which (unique) vector $x$ is it obtained?
$22$ with $x=(2,0,0)$
$24$ with $x=(1,0,1)$
$26$ with $x=(0,0,2)$
$26$ with $x=(2,0,0)$
Explanation. The DP $v(k)=\max_j\{p_j+v(k-w_j)\}$ gives $v(10)=26$, attained by $x=(0,0,2)$. The greedy by efficiency with repetitions gives $22$ and the 0-1 knapsack $24$.
Unbounded knapsack (UKP): $n=3$ item types, each in unlimited copies, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 11 & 6 & 12\\ w_j & 4 & 5 & 5\end{array}$, capacity $c=15$; $x_j$ is the number of copies of type $j$. What is the optimal value, and with which (unique) vector $x$ is it obtained?
$36$ with $x=(0,0,3)$
$33$ with $x=(3,0,0)$
$29$ with $x=(1,1,1)$
$36$ with $x=(3,0,0)$
Explanation. The DP $v(k)=\max_j\{p_j+v(k-w_j)\}$ gives $v(15)=36$, attained by $x=(0,0,3)$. The greedy by efficiency with repetitions gives $33$ and the 0-1 knapsack $29$.
Bounded knapsack (BKP): type $j$ has profit $p_j$, weight $w_j$ and $b_j$ copies, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 5 & 6 & 7\\ w_j & 2 & 2 & 2\\ b_j & 1 & 2 & 2\end{array}$, capacity $c=11$. $v(j,k)$ is the largest profit with types $1,\dots,j$ only and capacity $k$, with at most $b_j$ copies of type $j$. What is $v(2,5)$?
$11$
$5$
$12$
$14$
Explanation. With types $1$ and $2$ and capacity $5$, respecting the bounds $b_1=1$ and $b_2=2$, the maximum is $12$. Without bounds on the copies one would get $12$.
Bounded knapsack (BKP): type $j$ has profit $p_j$, weight $w_j$ and $b_j$ copies, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 11 & 6 & 9\\ w_j & 3 & 2 & 5\\ b_j & 1 & 3 & 3\end{array}$, capacity $c=12$. $v(j,k)$ is the largest profit with types $1,\dots,j$ only and capacity $k$, with at most $b_j$ copies of type $j$. What is $v(2,10)$?
$11$
$29$
$34$
$17$
Explanation. With types $1$ and $2$ and capacity $10$, respecting the bounds $b_1=1$ and $b_2=3$, the maximum is $29$. Without bounds on the copies one would get $34$.
Subset sum: weights $w=(12,3,6,11,9)$ and target $c=28$. $r(j,k)$ is true if some subset of the first $j$ weights sums to exactly $k$: $r(0,0)$ true, $r(0,k)$ false for $k\ge 1$, and $r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)$ (the second term only if $w_j\le k$). What is the largest $k\le c$ with $r(5,k)=\textit{true}$?
$27$
$26$
$21$
$18$
Explanation. The reachable sums not larger than $28$ have maximum $27$; $c=28$ is not reachable. The greedy choices (by non-increasing weight: $26$) do not guarantee the maximum.
Subset sum: weights $w=(12,10,14,12,10)$ and target $c=27$. $r(j,k)$ is true if some subset of the first $j$ weights sums to exactly $k$: $r(0,0)$ true, $r(0,k)$ false for $k\ge 1$, and $r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)$ (the second term only if $w_j\le k$). What is the largest $k\le c$ with $r(5,k)=\textit{true}$?
$20$
$22$
$26$
$27$
Explanation. The reachable sums not larger than $27$ have maximum $26$; $c=27$ is not reachable. The greedy choices (by non-increasing weight: $26$) do not guarantee the maximum.
Subset sum with weights $w=(6,6,8,8)$ and target $c=10$. $r(j,k)$ is true if a subset of the first $j$ weights sums to exactly $k$ (the empty subset gives $k=0$). For how many values $k\in\{0,1,\dots,10\}$ is the cell $r(4,k)$ true?
$3$
$5$
$2$
$11$
Explanation. The reachable sums up to $10$ are $3$, including $k=0$. Different subsets may give the same sum: the subsets with sum at most $10$ are $5$.
Subset sum with weights $w=(5,8,4,2)$ and target $c=13$. $r(j,k)$ is true if a subset of the first $j$ weights sums to exactly $k$ (the empty subset gives $k=0$). For how many values $k\in\{0,1,\dots,13\}$ is the cell $r(4,k)$ true?
$12$
$11$
$14$
$13$
Explanation. The reachable sums up to $13$ are $12$, including $k=0$. Different subsets may give the same sum: the subsets with sum at most $13$ are $12$.
6. DP for the multiple-choice knapsack problem (2)
Multiple-choice knapsack (MCKP): classes $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4\}$, $\mathscr{J}_3=\{5,6\}$, items $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 2 & 4 & 3 & 5 & 2 & 3\\ w_j & 1 & 4 & 3 & 5 & 4 & 6\end{array}$, capacity $c=10$; exactly one item per class is chosen. With $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$, $v(0,k)=0$, what is the optimal value $v(3,10)$?
$8$
$7$
$9$
$12$
Explanation. The optimal value is $9$. Ignoring the capacity one would take the best item of every class ($12$); with «at most one item per class» another problem would be solved ($9$).
Multiple-choice knapsack (MCKP): classes $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4\}$, $\mathscr{J}_3=\{5,6\}$, items $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 2 & 6 & 7 & 2 & 6 & 9\\ w_j & 6 & 5 & 5 & 1 & 1 & 2\end{array}$, capacity $c=9$; exactly one item per class is chosen. With $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$, $v(0,k)=0$, what is the optimal value $v(3,9)$?
$17$
$16$
$22$
$14$
Explanation. The optimal value is $17$. Ignoring the capacity one would take the best item of every class ($22$); with «at most one item per class» another problem would be solved ($17$).
Multidimensional knapsack (MDKP) with two dimensions of capacity $c_1=8$ and $c_2=9$; item $j$ has profit $p_j$ and weights $w_{1j}$, $w_{2j}$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 4 & 8 & 3 & 8\\ w_{1j} & 4 & 3 & 4 & 6\\ w_{2j} & 5 & 2 & 4 & 2\end{array}$. Every item is taken at most once. With the DP $v(j,(k_1,k_2))$ on both capacities, what is the optimal value?
$12$
$13$
$20$
$16$
Explanation. The optimal value is $12$. Considering a single dimension one would get $12$ or $20$, and adding the constraints $16$: these are relaxations, not MDKP solutions.
Multidimensional knapsack (MDKP) with two dimensions of capacity $c_1=9$ and $c_2=11$; item $j$ has profit $p_j$ and weights $w_{1j}$, $w_{2j}$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 5 & 8 & 5 & 10\\ w_{1j} & 2 & 4 & 4 & 6\\ w_{2j} & 6 & 3 & 1 & 4\end{array}$. Every item is taken at most once. With the DP $v(j,(k_1,k_2))$ on both capacities, what is the optimal value?
$16$
$23$
$18$
$15$
Explanation. The optimal value is $15$. Considering a single dimension one would get $15$ or $23$, and adding the constraints $18$: these are relaxations, not MDKP solutions.
Multidimensional knapsack (MDKP) with two dimensions of capacity $c_1=8$ and $c_2=7$; item $j$ has profit $p_j$ and weights $w_{1j}$, $w_{2j}$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 7 & 9 & 7 & 3\\ w_{1j} & 4 & 1 & 4 & 6\\ w_{2j} & 5 & 5 & 6 & 2\end{array}$. Every item is taken at most once. Which set of items is the (unique) optimal solution?
$\{1\}$
$\{2\}$
$\{1,2\}$
$\{2,4\}$
Explanation. $\{2,4\}$ respects both capacities and is worth $12$; the second best feasible solution is worth $9$.
Multidimensional knapsack (MDKP) with two dimensions of capacity $c_1=9$ and $c_2=10$; item $j$ has profit $p_j$ and weights $w_{1j}$, $w_{2j}$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 10 & 8 & 7 & 5\\ w_{1j} & 6 & 2 & 1 & 2\\ w_{2j} & 5 & 4 & 1 & 1\end{array}$. Every item is taken at most once. Which set of items is the (unique) optimal solution?
$\{1,2,3\}$
$\{2,3,4\}$
$\{1,2\}$
$\{1,3,4\}$
Explanation. $\{1,2,3\}$ respects both capacities and is worth $25$; the second best feasible solution is worth $22$.
Knapsack with setups (KPS): classes $\mathscr{J}_1=\{1,2\}$ and $\mathscr{J}_2=\{3,4\}$, items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 6 & 8 & 3 & 7\\ w_j & 3 & 5 & 5 & 4\end{array}$, capacity $c=9$. Using class $h$ costs once the setup profit $f_h$ and the setup weight $s_h$, with $f=(4,1)$ and $s=(3,1)$; the profit of the items minus the paid setups is maximized. What is the optimal value?
$8$
$10$
$7$
$6$
Explanation. The optimal value is $6$. Forgetting the setup costs gives $8$, forgetting the setup weights $10$, paying the setup for every item $6$.
Knapsack with setups (KPS): classes $\mathscr{J}_1=\{1,2\}$ and $\mathscr{J}_2=\{3,4\}$, items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 5 & 5 & 5 & 8\\ w_j & 5 & 1 & 5 & 4\end{array}$, capacity $c=11$. Using class $h$ costs once the setup profit $f_h$ and the setup weight $s_h$, with $f=(4,4)$ and $s=(2,3)$; the profit of the items minus the paid setups is maximized. What is the optimal value?
$5$
$13$
$10$
$6$
Explanation. The optimal value is $6$. Forgetting the setup costs gives $13$, forgetting the setup weights $10$, paying the setup for every item $5$.
Knapsack with setups (KPS): classes $\mathscr{J}_1=\{1,2\}$ and $\mathscr{J}_2=\{3,4\}$, items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 6 & 8 & 3 & 7\\ w_j & 3 & 5 & 5 & 4\end{array}$, capacity $c=9$. Using class $h$ costs once the setup profit $f_h$ and the setup weight $s_h$, with $f=(4,1)$ and $s=(3,1)$; the profit of the items minus the paid setups is maximized. Which set of items is the (unique) optimal solution?
$\{2\}$
$\{1\}$
$\{3\}$
$\{4\}$
Explanation. $\{4\}$ is worth $6$, setups included; the second best solution is worth $4$.
Knapsack with setups (KPS): classes $\mathscr{J}_1=\{1,2\}$ and $\mathscr{J}_2=\{3,4\}$, items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 5 & 5 & 5 & 8\\ w_j & 5 & 1 & 5 & 4\end{array}$, capacity $c=11$. Using class $h$ costs once the setup profit $f_h$ and the setup weight $s_h$, with $f=(4,4)$ and $s=(2,3)$; the profit of the items minus the paid setups is maximized. Which set of items is the (unique) optimal solution?
$\{2,3\}$
$\{2,4\}$
$\{4\}$
$\{1,2\}$
Explanation. $\{1,2\}$ is worth $6$, setups included; the second best solution is worth $5$.
Multiple knapsack (MKP): two knapsacks of capacity $c_1=5$ and $c_2=7$, items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 5 & 6 & 6 & 5\\ w_j & 2 & 4 & 4 & 2\end{array}$; every item goes into at most one knapsack. With the DP on the states $(j,(k_1,k_2))$ of residual capacities, what is the optimal value?
$22$
$17$
$16$
$11$
Explanation. The optimal value is $17$. A single knapsack of capacity $12$ would give $22$: it is an upper bound, since that solution cannot be split between the two knapsacks.
Multiple knapsack (MKP): two knapsacks of capacity $c_1=8$ and $c_2=7$, items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 6 & 5 & 6 & 9\\ w_j & 5 & 2 & 5 & 4\end{array}$; every item goes into at most one knapsack. With the DP on the states $(j,(k_1,k_2))$ of residual capacities, what is the optimal value?
$20$
$21$
$19$
$14$
Explanation. The optimal value is $20$. A single knapsack of capacity $15$ would give $21$: it is an upper bound, since that solution cannot be split between the two knapsacks.
Multiple knapsack (MKP): two knapsacks of capacity $c_1=6$ and $c_2=6$, items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 10 & 5 & 3 & 7\\ w_j & 2 & 2 & 3 & 2\end{array}$; every item goes into at most one knapsack. Which set of items is inserted into the knapsacks in the optimal solution (the optimal set is unique)?
$\{1,2,3\}$
$\{1,2,4\}$
$\{1,2,3,4\}$
$\{1,3,4\}$
Explanation. The set $\{1,2,3,4\}$, of value $25$, can be split between the two knapsacks respecting the capacities; the second best set is worth $22$.
Multiple knapsack (MKP): two knapsacks of capacity $c_1=8$ and $c_2=7$, items $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 9 & 3 & 5 & 4\\ w_j & 4 & 5 & 2 & 5\end{array}$; every item goes into at most one knapsack. Which set of items is inserted into the knapsacks in the optimal solution (the optimal set is unique)?
$\{1,2,3\}$
$\{1,4\}$
$\{1,3\}$
$\{1,3,4\}$
Explanation. The set $\{1,3,4\}$, of value $18$, can be split between the two knapsacks respecting the capacities; the second best set is worth $17$.
10. DP for the uncapacitated lot sizing problem (3)
Uncapacitated lot sizing (ULS): demand $d_t$, setup cost $sc_t$, unit variable cost $vc_t$ and unit cost $hc_t$ of the stock at the end of the period $\begin{array}{c|cccc}t & 1 & 2 & 3 & 4\\ \hline d_t & 20 & 5 & 30 & 10\\ sc_t & 70 & 90 & 30 & 30\\ vc_t & 2 & 1 & 2 & 0\\ hc_t & 3 & 2 & 1 & 1\end{array}$. What is the cost $c_{2,4}$ of the production run in period $2$ covering the demands of periods $2,\dots,4$ (setup, production and stock)?
$225$
$135$
$275$
$205$
Explanation. $c_{j,t}=sc_j+vc_j\,D_{j,t}+\sum_{k=j}^{t-1}hc_k\,D_{k+1,t}=225$: at the end of each period $k$ the stock contains the demands of all the following periods of the run, not only that of the next period.
Uncapacitated lot sizing (ULS): demand $d_t$, setup cost $sc_t$, unit variable cost $vc_t$ and unit cost $hc_t$ of the stock at the end of the period $\begin{array}{c|cccc}t & 1 & 2 & 3 & 4\\ \hline d_t & 15 & 15 & 30 & 25\\ sc_t & 90 & 90 & 90 & 40\\ vc_t & 0 & 2 & 1 & 2\\ hc_t & 1 & 2 & 3 & 3\end{array}$. What is the cost $c_{2,4}$ of the production run in period $2$ covering the demands of periods $2,\dots,4$ (setup, production and stock)?
$610$
$325$
$365$
$415$
Explanation. $c_{j,t}=sc_j+vc_j\,D_{j,t}+\sum_{k=j}^{t-1}hc_k\,D_{k+1,t}=415$: at the end of each period $k$ the stock contains the demands of all the following periods of the run, not only that of the next period.
Uncapacitated lot sizing (ULS) with $m=4$ periods, setup cost $sc_t=70$, zero variable cost and holding cost $hc_t=1$ in every period, and demands $\begin{array}{c|cccc}t & 1 & 2 & 3 & 4\\ \hline d_t & 25 & 35 & 35 & 5\end{array}$. Let $c_{j,t}$ be the cost of the run produced in $j$ for periods $j,\dots,t$ and $v(t)$ the minimum cost of covering periods $1,\dots,t$: $v(0)=0$ and $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$. What is the optimal cost $v(4)$?
$180$
$190$
$280$
$245$
Explanation. $v=(0,70,105,175,180)$ for $t=0,\dots,4$; runs in periods $1,3$. A setup in every period costs $280$, a single run in period 1 costs $190$.
Uncapacitated lot sizing (ULS) with $m=4$ periods, setup cost $sc_t=100$, zero variable cost and holding cost $hc_t=1$ in every period, and demands $\begin{array}{c|cccc}t & 1 & 2 & 3 & 4\\ \hline d_t & 35 & 30 & 40 & 35\end{array}$. Let $c_{j,t}$ be the cost of the run produced in $j$ for periods $j,\dots,t$ and $v(t)$ the minimum cost of covering periods $1,\dots,t$: $v(0)=0$ and $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$. What is the optimal cost $v(4)$?
$265$
$400$
$310$
$315$
Explanation. $v=(0,100,130,210,265)$ for $t=0,\dots,4$; runs in periods $1,3$. A setup in every period costs $400$, a single run in period 1 costs $315$.
Example 1 · dp-g-uls-completa · level complessa · notes
Uncapacitated lot sizing (ULS) with zero variable cost, demand $d_t$, setup cost $sc_t$ and unit cost $hc_t$ of the stock at the end of the period $\begin{array}{c|ccccc}t & 1 & 2 & 3 & 4 & 5\\ \hline d_t & 25 & 35 & 25 & 5 & 15\\ sc_t & 70 & 40 & 70 & 90 & 40\\ hc_t & 2 & 2 & 2 & 1 & 1\end{array}$. With $c_{j,t}$ the cost of the run produced in $j$ for periods $j,\dots,t$, the DP is $v(0)=0$, $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$. What are the optimal cost $v(5)$ and the periods of the production runs?
$v(5)=310$, runs in periods $1,2,3,4,5$
$v(5)=220$, runs in periods $1,2,5$
$v(5)=375$, runs in periods $1$
$v(5)=230$, runs in periods $1,2,3,5$
Explanation. $v=(0,70,110,160,180,220)$ for $t=0,\dots,5$; going back through the argmins gives runs in periods $1,2,5$. By the Wagner–Whitin property it is enough to compare the runs $c_{j,t}$.
Example 2 · dp-g-uls-completa · level complessa · notes
Uncapacitated lot sizing (ULS) with zero variable cost, demand $d_t$, setup cost $sc_t$ and unit cost $hc_t$ of the stock at the end of the period $\begin{array}{c|ccccc}t & 1 & 2 & 3 & 4 & 5\\ \hline d_t & 40 & 10 & 5 & 10 & 35\\ sc_t & 80 & 70 & 40 & 40 & 50\\ hc_t & 2 & 2 & 1 & 2 & 2\end{array}$. With $c_{j,t}$ the cost of the run produced in $j$ for periods $j,\dots,t$, the DP is $v(0)=0$, $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$. What are the optimal cost $v(5)$ and the periods of the production runs?
$v(5)=210$, runs in periods $1,4,5$
$v(5)=200$, runs in periods $1,3,5$
$v(5)=280$, runs in periods $1,2,3,4,5$
$v(5)=415$, runs in periods $1$
Explanation. $v=(0,80,100,120,150,200)$ for $t=0,\dots,5$; going back through the argmins gives runs in periods $1,3,5$. By the Wagner–Whitin property it is enough to compare the runs $c_{j,t}$.
Capacitated lot sizing (CLS) over $3$ periods: demand $d_t$, capacity $cap_t$, setup cost $sc_t$ (paid if we produce in period $t$) and cost $hc_t$ per unit of stock at the end of a period, zero variable cost, zero initial and final stock: $\begin{array}{c|ccc}t & 1 & 2 & 3\\ \hline d_t & 4 & 5 & 2\\ cap_t & 6 & 6 & 6\\ sc_t & 14 & 13 & 11\\ hc_t & 2 & 1 & 3\end{array}$. With the DP on the states $(t,k)$ (period, final stock), what is the optimal cost $v(3,0)$?
$31$
$38$
$29$
$32$
Explanation. The optimal cost is $31$, with the plan $x=(5,6,0)$. The lot-for-lot plan costs $38$; ignoring the capacities one would get $29$.
Capacitated lot sizing (CLS) over $3$ periods: demand $d_t$, capacity $cap_t$, setup cost $sc_t$ (paid if we produce in period $t$) and cost $hc_t$ per unit of stock at the end of a period, zero variable cost, zero initial and final stock: $\begin{array}{c|ccc}t & 1 & 2 & 3\\ \hline d_t & 2 & 2 & 5\\ cap_t & 7 & 7 & 6\\ sc_t & 8 & 13 & 12\\ hc_t & 1 & 2 & 3\end{array}$. With the DP on the states $(t,k)$ (period, final stock), what is the optimal cost $v(3,0)$?
$23$
$33$
$22$
$25$
Explanation. The optimal cost is $22$, with the plan $x=(4,0,5)$. The lot-for-lot plan costs $33$; ignoring the capacities one would get $22$.
Example 1 · dp-g-cls-plan · level complessa · notes
Capacitated lot sizing (CLS) over $3$ periods: demand $d_t$, capacity $cap_t$, setup cost $sc_t$ (paid if we produce in period $t$) and cost $hc_t$ per unit of stock at the end of a period, zero variable cost, zero initial and final stock: $\begin{array}{c|ccc}t & 1 & 2 & 3\\ \hline d_t & 3 & 1 & 5\\ cap_t & 5 & 7 & 3\\ sc_t & 13 & 11 & 14\\ hc_t & 3 & 2 & 1\end{array}$. Which production plan $x=(x_1,x_2,x_3)$ is optimal (the optimal plan is unique), and what does it cost?
$x=(3,3,3)$, cost $42$
$x=(5,4,0)$, cost $40$
$x=(3,6,0)$, cost $34$
$x=(4,5,0)$, cost $37$
Explanation. The DP on stocks and the reconstruction give $x=(3,6,0)$ with cost $34$; the second best plan costs $37$. With capacities production can anticipate demand even with positive incoming stock.
Example 2 · dp-g-cls-plan · level complessa · notes
Capacitated lot sizing (CLS) over $3$ periods: demand $d_t$, capacity $cap_t$, setup cost $sc_t$ (paid if we produce in period $t$) and cost $hc_t$ per unit of stock at the end of a period, zero variable cost, zero initial and final stock: $\begin{array}{c|ccc}t & 1 & 2 & 3\\ \hline d_t & 2 & 2 & 5\\ cap_t & 7 & 7 & 6\\ sc_t & 8 & 13 & 12\\ hc_t & 1 & 2 & 3\end{array}$. Which production plan $x=(x_1,x_2,x_3)$ is optimal (the optimal plan is unique), and what does it cost?
$x=(5,0,4)$, cost $25$
$x=(2,2,5)$, cost $33$
$x=(4,0,5)$, cost $22$
$x=(6,0,3)$, cost $28$
Explanation. The DP on stocks and the reconstruction give $x=(4,0,5)$ with cost $22$; the second best plan costs $25$. With capacities production can anticipate demand even with positive incoming stock.
Coin change (CCP): denominations $w=(1,5,12)$, in unlimited supply; an amount of exactly $c=21$ must be paid with the minimum number of coins. $v(k)$ is the minimum number of coins for amount $k$: $v(0)=0$ and $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$. What is $v(21)$?
$6$
$10$
$5$
$4$
Explanation. The DP gives $v(21)=5$ coins. The greedy that always uses the largest denomination uses $6$: with these denominations it is not optimal.
Coin change (CCP): denominations $w=(1,6,9)$, in unlimited supply; an amount of exactly $c=22$ must be paid with the minimum number of coins. $v(k)$ is the minimum number of coins for amount $k$: $v(0)=0$ and $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$. What is $v(22)$?
$6$
$4$
$5$
$3$
Explanation. The DP gives $v(22)=4$ coins. The greedy that always uses the largest denomination uses $6$: with these denominations it is not optimal.
Example 1 · dp-g-ccp-unreach · level media · notes
Coin change (CCP) with denominations $w=(4,7)$ in unlimited supply. $v(k)$ is the minimum number of coins to pay exactly the amount $k$: $v(0)=0$, $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, and $v(k)=+\infty$ if the amount cannot be paid. For how many values $k\in\{1,\dots,18\}$ is $v(k)=+\infty$?
$10$
$12$
$9$
$8$
Explanation. Computing $v(1),\dots,v(18)$ one finds $9$ unobtainable amounts. Excluding the multiples of $4$ and $7$ is not enough: their sums are obtainable too.
Example 2 · dp-g-ccp-unreach · level media · notes
Coin change (CCP) with denominations $w=(4,9)$ in unlimited supply. $v(k)$ is the minimum number of coins to pay exactly the amount $k$: $v(0)=0$, $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, and $v(k)=+\infty$ if the amount cannot be paid. For how many values $k\in\{1,\dots,13\}$ is $v(k)=+\infty$?
$5$
$7$
$9$
$8$
Explanation. Computing $v(1),\dots,v(13)$ one finds $8$ unobtainable amounts. Excluding the multiples of $4$ and $9$ is not enough: their sums are obtainable too.
Rod cutting (RCP): a rod of length $n=6$ is cut into pieces of integer length, and the piece of length $j$ is sold at $p_j$: $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 5 & 6 & 11 & 12 & 14 & 15\end{array}$. $v(\ell)$ is the largest revenue from a rod of length $\ell$: $v(0)=0$ and $v(\ell)=\max_{1\le j\le \ell}\{p_j+v(\ell-j)\}$. What is $v(6)$?
$22$
$15$
$25$
$30$
Explanation. $v=(0,5,10,15,20,25,30)$ for $\ell=0,\dots,6$, hence $v(6)=30$. A single cut ($22$) or the piece with the best ratio $p_j/j$ ($30$) are not enough in general.
Rod cutting (RCP): a rod of length $n=6$ is cut into pieces of integer length, and the piece of length $j$ is sold at $p_j$: $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 3 & 4 & 5 & 7 & 9 & 10\end{array}$. $v(\ell)$ is the largest revenue from a rod of length $\ell$: $v(0)=0$ and $v(\ell)=\max_{1\le j\le \ell}\{p_j+v(\ell-j)\}$. What is $v(6)$?
$10$
$18$
$15$
$12$
Explanation. $v=(0,3,6,9,12,15,18)$ for $\ell=0,\dots,6$, hence $v(6)=18$. A single cut ($12$) or the piece with the best ratio $p_j/j$ ($18$) are not enough in general.
Rod cutting (RCP): a rod of length $n=6$ is cut into pieces of integer length, and the piece of length $j$ sells at $p_j$: $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 3 & 7 & 12 & 13 & 18 & 22\end{array}$. What is the largest revenue and with which pieces (unique optimal cut, up to order)?
$22$: pieces $6$
$24$: pieces $3+3$
$18$: pieces $1+1+1+1+1+1$
$22$: pieces $3+2+1$
Explanation. The DP $v(\ell)=\max_j\{p_j+v(\ell-j)\}$ gives $v(6)=24$ with pieces $3+3$. Selling the whole rod gives $22$.
Rod cutting (RCP): a rod of length $n=5$ is cut into pieces of integer length, and the piece of length $j$ sells at $p_j$: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 5 & 7 & 8 & 10 & 15\end{array}$. What is the largest revenue and with which pieces (unique optimal cut, up to order)?
$25$: pieces $1+1+1+1+1$
$22$: pieces $2+1+1+1$
$15$: pieces $5$
$19$: pieces $2+2+1$
Explanation. The DP $v(\ell)=\max_j\{p_j+v(\ell-j)\}$ gives $v(5)=25$ with pieces $1+1+1+1+1$. Selling the whole rod gives $15$.