← Back to the site

Question bank

315 fixed questions · 25 generated questions

Fixed questions (315)

1. Principles of dynamic programming (33)

dp-f-001 · level facile · notes
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?
  1. Optimal substructure and overlapping subproblems
  2. Optimal substructure and independent subproblems
  3. Linear objective function and integer constraints
  4. 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.
dp-f-002 · level facile · notes
In dynamic programming (DP), what happens if a problem has optimal substructure but every subproblem appears only once in the recursion?
  1. The table makes the algorithm polynomial in the input size
  2. The recurrence becomes wrong and needs more base cases
  3. The table must be filled top-down, not bottom-up
  4. The table gives no advantage: the algorithm is a plain recursion
Explanation. Without overlapping subproblems there is nothing to reuse. Without the optimal substructure, instead, the recurrence would be wrong.
dp-f-003 · level facile · notes
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?
  1. Reading only the table of values forward, from the initial to the final state
  2. Re-running the recursion top-down, without any memorization
  3. Storing the decisions in another table and reading them backward from the final state
  4. 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).
dp-f-040 · level facile · notes
A dynamic programming (DP) algorithm follows the «divide, conquer and combine» paradigm. What does the combining principle say?
  1. The best subproblem is chosen and the others are discarded
  2. An optimal solution of the problem is built from optimal solutions of the subproblems
  3. The problem is decomposed into smaller subproblems of the same type
  4. 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.
dp-f-041 · level facile · notes
For the knapsack problem with $n$ items brute force lists the $2^n$ subsets. How does dynamic programming (DP) avoid this enumeration?
  1. It stores the optimal value of every subproblem in a table and reuses it when the subproblem appears again
  2. It discards a priori the subsets with low profit, as a greedy heuristic
  3. It solves the LP relaxation and rounds the solution
  4. 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).
dp-f-042 · level facile · notes
In dynamic programming (DP) the subproblems generated by the decomposition are «independent». What does this mean?
  1. Each appears only once in the recursion
  2. They all have the same size
  3. Their optimal solutions have no element in common
  4. 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.
dp-f-043 · level facile · notes
In dynamic programming (DP), what does the optimal substructure property of a recursive decomposition state?
  1. Every optimal solution of a subproblem is also optimal for the problem
  2. The subproblems repeat many times in the recursion
  3. An optimal solution of the problem is obtained by combining optimal solutions of its subproblems
  4. 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.
dp-f-044 · level facile · notes
What is the first step in the design of a dynamic programming (DP) algorithm?
  1. Compute an upper bound with a heuristic
  2. Identify the recursive decomposition into subproblems and check optimal substructure and overlapping subproblems
  3. Write the integer linear programming model and its relaxation
  4. 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.
dp-f-045 · level facile · notes
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?
  1. An order of the subproblems in which each comes after those it depends on
  2. That the subproblems never repeat
  3. That the table is filled in random order
  4. 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.
dp-f-046 · level facile · notes
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)?
  1. The DP for the 0-1 knapsack, $\Theta(nc)$
  2. The DP for the bounded knapsack, $\Theta(nc\,b_{\max})$
  3. The DP for capacitated lot sizing, $O(mDC)$
  4. 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.
dp-f-047 · level facile · notes
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?
  1. Never, since the vector makes the problem strongly polynomial
  2. Only when all the capacities are equal
  3. Only for a fixed number $m$ of dimensions or knapsacks
  4. 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$.
dp-f-048 · level facile · notes
In a dynamic programming (DP) algorithm, what does the lookup table contain?
  1. The subproblems still to be solved, in priority order
  2. The optimal value of every subproblem already solved, read when the subproblem appears again
  3. The list of all feasible solutions of the problem
  4. 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.
dp-f-191 · level ipotesi · notes
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?
  1. The DP becomes polynomial
  2. The table has fewer cells
  3. Combining the optimal values of the subproblems may give a non-optimal solution, and the recursion is not correct
  4. 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.
dp-f-192 · level facile · notes
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?
  1. Uncapacitated lot sizing and knapsack with setups
  2. Multidimensional knapsack and multiple knapsack, with one state for every capacity vector
  3. 0/1 knapsack and subset sum
  4. 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.
dp-f-193 · level teorema · notes
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?
  1. The subproblems repeat, and the DP solves each one only once storing its value in the table
  2. Because the DP examines fewer feasible solutions per subproblem
  3. Because the DP uses a different recursion
  4. 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.
dp-f-194 · level facile · notes
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)?
  1. The DP becomes incorrect
  2. The DP becomes polynomial
  3. The table has more cells than subproblems
  4. 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.
dp-f-195 · level facile · notes
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?
  1. From the largest subproblem to the smallest
  2. Only along the diagonal
  3. In an order where every subproblem comes after all those it depends on
  4. 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.
dp-f-196 · level facile · notes
Among the dynamic programming algorithms of the module, which have a number of steps polynomial in the instance size, and not only pseudo-polynomial?
  1. All of them
  2. Wagner-Whitin for uncapacitated lot sizing ($\Theta(m^2)$) and rod cutting ($\Theta(n^2)$)
  3. The DP of the 0/1 knapsack and that of the subset sum
  4. 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.
dp-f-250 · level teorema · notes
A problem has optimal substructure and overlapping subproblems. What does a dynamic programming (DP) algorithm based on a correct recurrence guarantee?
  1. An optimal solution in time polynomial in the input
  2. A solution with a guaranteed approximation ratio
  3. Each subproblem solved as many times as it appears
  4. 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.
dp-f-251 · level ipotesi · notes
In dynamic programming (DP), which property of the problem makes the recurrence correct, that is, makes it give the optimal value?
  1. Integer positive data
  2. A polynomial number of subproblems
  3. Optimal substructure
  4. 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.
dp-f-252 · level ipotesi · notes
In dynamic programming (DP), which property makes it worth storing the values of the subproblems in a table?
  1. A unique optimal solution
  2. Overlapping subproblems
  3. Optimal substructure
  4. A linear objective
Explanation. If the same subproblem appears several times in the recursion, the table avoids computing it again.
dp-f-253 · level ipotesi · notes
In the bottom-up approach of dynamic programming, which condition must the order of filling the table satisfy?
  1. Each value comes after the values it depends on
  2. The values come in decreasing order
  3. The base cases are computed last
  4. None: the order does not matter
Explanation. The recurrence uses values of smaller subproblems: they must already be in the table when needed.
dp-f-254 · level teorema · notes
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?
  1. $O(S+d)$
  2. $O(S^{d})$
  3. $O(d^{S})$
  4. $O(S\,d)$
Explanation. Each subproblem is computed once, with $O(d)$ steps: $O(S\,d)$ in total.
dp-f-255 · level teorema · notes
What distinguishes dynamic programming (DP) from the plain recursive «divide and conquer» approach?
  1. DP finds only approximate solutions
  2. DP uses neither recurrences nor base cases
  3. DP stores the values and does not recompute them
  4. DP uses subproblems of a different type
Explanation. Both divide into subproblems of the same type; DP stores the values in a table and solves each subproblem once.
dp-f-256 · level ipotesi · notes
In the design of a DP algorithm, what are the base cases of the recurrence for?
  1. They remove the overlapping subproblems
  2. They give the values of the smallest subproblems, from which all others start
  3. They give the optimal solution of the problem directly
  4. They are needed only in the top-down approach
Explanation. Without base cases the recurrence does not close: their values are known without recursion and all others are computed from them.
dp-f-257 · level teorema · notes
In a DP algorithm the optimal value is computed by the recurrence (step 1). How is an optimal solution obtained (step 2)?
  1. The choice made in each cell is stored and traced backwards
  2. The problem is solved again with an ILP solver
  3. The cell of maximum value of each row is taken
  4. The table is sorted by decreasing values
Explanation. An additional table records which term of the recurrence gave the value: reading it backwards from the last cell rebuilds a solution.
dp-f-299 · level facile · notes
What kind of algorithm is a dynamic programming (DP) algorithm?
  1. An approximation algorithm
  2. A local search method
  3. An exact algorithm
  4. A heuristic without guarantee
Explanation. DP combines the optimal solutions of the subproblems and finds an optimal solution: it is an exact algorithm.
dp-f-300 · level facile · notes
In the top-down approach with memoization, what does a recursive call on an already solved subproblem do?
  1. It stops the algorithm
  2. It returns the value stored in the table
  3. It recomputes the value from scratch
  4. It returns $0$
Explanation. The table stores the values already computed: a second call reads them instead of recomputing them.
dp-f-301 · level facile · notes
What is the difference between the top-down and the bottom-up approach of DP?
  1. Top-down starts from the problem and recurs; bottom-up fills the table from the base cases
  2. Top-down is exact, bottom-up is heuristic
  3. Bottom-up does not use the recurrence
  4. Top-down does not use base cases
Explanation. They use the same recurrence and give the same value; only the order of computing the subproblems changes.
dp-f-302 · level facile · notes
What does it mean that a problem has optimal substructure?
  1. Every subproblem has a unique solution
  2. The subproblems are independent
  3. The problem has few subproblems
  4. An optimal solution contains optimal solutions of its subproblems
Explanation. It is the property that allows writing the optimal value with a recurrence on the optimal values of the subproblems.
dp-f-303 · level facile · notes
What does it mean that a problem has overlapping subproblems?
  1. Each subproblem appears only once
  2. The subproblems are of different types
  3. The same subproblems appear several times in the recursion
  4. The subproblems share solutions
Explanation. It is what makes the table useful: each subproblem is computed once and then reused.
dp-f-304 · level facile · notes
In the DP algorithms of the course, what are the two steps?
  1. The LP relaxation, then rounding
  2. The optimal value by the recurrence, then an optimal solution from the additional table
  3. A lower bound, then an upper bound
  4. A heuristic solution, then local search
Explanation. A recurrence with its base cases gives the optimal value; an additional table, read backwards, gives an optimal solution.
dp-f-305 · level facile · notes
Computing the Fibonacci numbers with the plain recursion $F(n)=F(n-1)+F(n-2)$ takes exponential time. What changes with DP?
  1. Each $F(k)$ is computed once: $\Theta(n)$ steps
  2. Nothing: the time stays exponential
  3. The time becomes $\Theta(\log n)$ without table
  4. The result changes
Explanation. The subproblems $F(k)$ repeat many times in the recursion; with the table each one is computed once.

2. DP for the 0/1 knapsack problem (38)

dp-f-004 · level facile · notes
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$?
  1. Otherwise $v[k-w_j]$ would not be computed yet, and the recurrence would read empty cells
  2. This way the number of steps drops from $\Theta(nc)$ to $\Theta(c)$, since half the vector is skipped
  3. This way the cell $v[c]$, which contains the optimal value, is filled first
  4. 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)$.
dp-f-005 · level facile · notes
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?
  1. $\max\{u(n,q): q\in\{0,\dots,P\}\}$
  2. $u(n,c)$
  3. $\max\{q\in\{0,\dots,P\}: u(n,q)\le c\}$
  4. $\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.
dp-f-006 · level facile · notes
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?
  1. $j$ decreases by $1$ and $k$ decreases by $p_j$
  2. $j$ decreases by $1$ and $k$ decreases by $w_j$
  3. $j$ decreases by $1$ and $k$ stays the same
  4. $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)$).
dp-f-049 · level facile · notes
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$?
  1. $40$
  2. $16$
  3. $50$
  4. $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.
dp-f-050 · level facile · notes
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?
  1. $5$
  2. $3$
  3. $4$
  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.
dp-f-051 · level facile · notes
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?
  1. Non-dominated states have pairwise different weights, and the possible integer weights are $0,1,\dots,c$
  2. Every item adds at most one state to the list
  3. Non-dominated states all have the same profit
  4. 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\}$.
dp-f-052 · level facile · notes
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?
  1. Because $(w',p')$ is infeasible
  2. Because dominated states always weigh more than the capacity
  3. Because the list must have at most $n$ elements
  4. 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.
dp-f-053 · level facile · notes
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)$?
  1. $50$
  2. $140$
  3. $145$
  4. $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.
dp-f-054 · level facile · notes
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)$?
  1. $8$
  2. $7$
  3. $+\infty$
  4. $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.
dp-f-055 · level facile · notes
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?
  1. $6$
  2. $8$
  3. $5$
  4. $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$.
dp-f-056 · level facile · notes
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?
  1. At every step: states heavier than $c$ are discarded at once
  2. At the start: items heavier than $c/2$ are discarded
  3. Never: the optimal value is the largest profit in $L_n$
  4. 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$.
dp-f-057 · level facile · notes
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?
  1. $14$
  2. $11$
  3. $15$
  4. $19$
Explanation. Among the states of weight at most $9$ the largest profit is $15$, of state $(9,15)$. $(11,19)$ exceeds the capacity.
dp-f-157 · level facile · notes
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$)?
  1. $4$
  2. $5$
  3. $6$
  4. $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.
dp-f-158 · level facile · notes
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?
  1. $21$
  2. $14$
  3. $15$
  4. $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.
dp-f-159 · level facile · notes
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?
  1. The solution $\{1,3\}$, of weight $5\le c$ and profit $14$
  2. The solution $\{2\}$, of weight $3$ and profit $7$
  3. An infeasible solution of weight $8$
  4. 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.
dp-f-160 · level teorema · notes
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)?
  1. Both grow $1000$ times
  2. The steps do not change, since the optimal solution is the same
  3. The steps grow about $10$ times
  4. 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.
dp-f-161 · level facile · notes
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?
  1. The vector requires $\Theta(nc^2)$ steps
  2. Identical also in memory
  3. Same number of steps $\Theta(nc)$; the vector uses memory $\Theta(c)$ instead of $\Theta(nc)$
  4. 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.
dp-f-162 · level facile · notes
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?
  1. $300$
  2. $8$, because $|L_j|\le\min\{2^j,c+1\}$
  3. $101$
  4. $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.
dp-f-163 · level teorema · notes
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)$?
  1. When the profits are small and the capacity is large ($P\ll c$)
  2. When the capacity is small and the profits large
  3. Always, because $\Theta(nP)$ is polynomial
  4. 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.
dp-f-164 · level facile · notes
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?
  1. Because the lists ignore the heavy items
  2. Because the lists store only the last row
  3. It is not: they always have $(n+1)(P+1)$ elements
  4. 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.
dp-f-197 · level facile · notes
0/1 knapsack with $n$ items: how many subsets of items are there, and how many of them does the DP consider explicitly?
  1. $n!$ subsets; the DP considers $n^2$ of them
  2. $n^2$ subsets; the DP considers all of them
  3. $2^n$ subsets; the DP does not enumerate them, but computes $(n+1)(c+1)$ values $v(j,k)$
  4. $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.
dp-f-198 · level facile · notes
In the 0/1 knapsack with $c=5$, $p=(6,7,8)$ and $w=(2,3,3)$, which binary vectors $(x_1,x_2,x_3)$ are infeasible?
  1. $(0,1,1)$, $(1,1,0)$ and $(1,1,1)$
  2. $(0,1,1)$ and $(1,1,1)$
  3. $(1,1,0)$ and $(1,0,1)$
  4. Only $(1,1,1)$
Explanation. $(0,1,1)$ weighs $6$ and $(1,1,1)$ weighs $8$, both above $c=5$; $(1,1,0)$ and $(1,0,1)$ weigh exactly $5$.
dp-f-199 · level facile · notes
In the 0/1 knapsack a solution is encoded by a binary vector $(x_1,\dots,x_n)$. Which two linear quantities are computed from the vector?
  1. The weight $\sum_jw_jx_j$, to compare with $c$, and the profit $\sum_jp_jx_j$, to maximize
  2. The number of items $\sum_jx_j$ and the maximum weight
  3. The average profit and the average weight
  4. The product of the weights and the product of the profits
Explanation. Feasibility and value are two weighted sums of the vector: this is what makes the knapsack an ILP problem with a single constraint.
dp-f-200 · level facile · notes
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?
  1. $86$; $\Theta(n+c)$
  2. $60$; $\Theta(nc)$
  3. $96$; $\Theta(n^2c)$
  4. $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$.
dp-f-201 · level facile · notes
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?
  1. Because Merge sorts the lists in $\Theta(c\log c)$
  2. Because the lists ignore the capacity
  3. Every list has at most $c+1$ states (distinct weights in $\{0,\dots,c\}$), and Merge scans them once per item
  4. 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.
dp-f-202 · level facile · notes
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?
  1. $8$
  2. $24$, i.e., $(n+1)(c+1)$
  3. $11$
  4. $15$
Explanation. $(3+1)(5+1)=24$ cells, against $11$ states overall in the lists: the lists store only reachable, non-dominated states.
dp-f-203 · level facile · notes
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$?
  1. $365$
  2. $252$
  3. $86$
  4. $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$.
dp-f-204 · level facile · notes
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?
  1. $\Theta(nP)$, as the matrix
  2. $\Theta(c)$
  3. $\Theta(n)$
  4. $\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.
dp-f-205 · level facile · notes
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?
  1. $2$
  2. $21$
  3. $4$, because $|L_j|\le\min\{2^j,P+1\}$
  4. $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.
dp-f-206 · level facile · notes
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)$?
  1. $84$
  2. $88$
  3. $63$
  4. $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$.
dp-f-207 · level teorema · notes
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?
  1. 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$
  2. The second DP ignores the weights
  3. In the second the lists are sorted by weight
  4. 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.
dp-f-258 · level ipotesi · notes
The DP for the 0/1 knapsack problem (KP) uses the values $v(j,k)$ for the capacities $k=0,1,\dots,c$. Which hypothesis on the data is needed?
  1. Pairwise distinct weights $w_j$
  2. Integer weights $w_j$ and capacity $c$
  3. Integer profits $p_j$
  4. Items sorted by efficiency
Explanation. The indices $k$ are the residual capacities $0,1,\dots,c$: integer weights and capacity are needed; profits can be arbitrary.
dp-f-259 · level teorema · notes
The DP for the 0/1 knapsack executes $\Theta(nc)$ steps. Why is this time not polynomial in the input size?
  1. $c$ is written with $O(\log c)$ bits and the time grows with the value $c$
  2. Because the table has $2^n$ cells
  3. Because each cell needs $\Theta(n)$ comparisons
  4. Because $n$ is not known in advance
Explanation. A time proportional to the value $c$ is exponential in its length in bits: it is pseudo-polynomial.
dp-f-260 · level teorema · notes
In the DP for the 0/1 knapsack with a single vector of $c+1$ cells, the capacities $k$ are scanned downwards. Why?
  1. So the comparisons are halved
  2. So item $j$ can be used several times
  3. Because small capacities are not needed
  4. So $v(k-w_j)$ is still the value without item $j$
Explanation. Cell $k-w_j$ is not updated yet: item $j$ is used at most once. Scanning upwards would give the unbounded knapsack.
dp-f-261 · level ipotesi · notes
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?
  1. An even capacity $c$
  2. Pairwise distinct profits $p_j$
  3. Integer profits $p_j$
  4. Integer weights $w_j$
Explanation. The indices $q$ are the profits $0,1,\dots,P$: integer profits are needed; weights can be arbitrary.
dp-f-262 · level teorema · notes
In the DP by profits for the 0/1 knapsack, $u(n,q)$ is the minimum weight to obtain the profit $q$. How is the optimal value with capacity $c$ read?
  1. The largest $u(n,q)$
  2. The largest $q$ with $u(n,q)\le c$
  3. The smallest $q$ with $u(n,q)\ge c$
  4. The value $u(n,P)$
Explanation. Profit $q$ is obtained without exceeding the capacity if and only if $u(n,q)\le c$: the optimal value is the largest such $q$.
dp-f-263 · level teorema · notes
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?
  1. When $P<c$
  2. When $c<P$
  3. When all weights are $1$
  4. Never
Explanation. The two times differ only by the factor $c$ or $P$: with small profits the DP by profits is better.
dp-f-264 · level ipotesi · notes
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?
  1. $W'\ge W$ and $Q'\ge Q$
  2. $W'+Q'\ge W+Q$
  3. $W'\le W$ and $Q'\le Q$
  4. $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.

3. DP for the unbounded knapsack problem (25)

dp-f-007 · level facile · notes
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$?
  1. $p_j+v(j-1,k)$, which does not reduce the capacity
  2. $v(j-1,k)$, which excludes type $j$
  3. $p_j+v(j,k-w_j)$, which stays in row $j$
  4. $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.
dp-f-008 · level facile · notes
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$?
  1. $v(k-1)$: the previous capacity is used
  2. $0$: part of the capacity may stay unused
  3. $-\infty$: the capacity must be filled exactly
  4. $+\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.
dp-f-009 · level facile · notes
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?
  1. $c+1$ cells, $\Theta(nc)$ steps
  2. $c$ cells, $\Theta(c)$ steps
  3. $(n+1)(c+1)$ cells, $\Theta(nc)$ steps
  4. $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.
dp-f-058 · level facile · notes
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?
  1. $27$
  2. $8$
  3. $60$
  4. $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.
dp-f-059 · level facile · notes
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)$?
  1. $8$
  2. $12$
  3. $11$
  4. $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$.
dp-f-060 · level facile · notes
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$?
  1. Read $s(c)$: all the copies are of that type
  2. Take one copy of type $s(k)$ and set $k\leftarrow k-w_{s(k)}$, until no type fits
  3. Take type $s(k)$ and move to the next type, as in the KP
  4. 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.
dp-f-061 · level facile · notes
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?
  1. Row by row (increasing $j$) and, in every row, by increasing $k$
  2. Row by row and, in every row, by decreasing $k$
  3. Column by column, by decreasing $j$
  4. 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$.
dp-f-062 · level facile · notes
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)$?
  1. $11$
  2. $3$
  3. $10$
  4. $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.
dp-f-063 · level facile · notes
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?
  1. The first takes $\Theta(nc)$ steps, the second $\Theta(n^2c)$
  2. They have the same number of cells, but the second is exponential
  3. The first has $c+1$ cells, the second $(n+1)(c+1)$; both take $\Theta(nc)$ steps
  4. 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.
dp-f-064 · level facile · notes
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$?
  1. Because $-\infty$ cannot be stored in a table
  2. The knapsack need not be filled: with no type available the empty solution is feasible and worth $0$
  3. Because profits are positive, so no value is negative
  4. 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.
dp-f-065 · level facile · notes
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?
  1. The cells $v(k-w_j)$, one for every type $j$ with $w_j\le k$
  2. Only the cell $v(k-1)$
  3. All the cells $v(0),\dots,v(k-1)$
  4. 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.
dp-f-066 · level facile · notes
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$?
  1. Nothing: with unlimited copies no type is dominated
  2. Use it only to fill the residual capacity
  3. Remove type $i$ instead, which has smaller weight
  4. 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$.
dp-f-165 · level facile · notes
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?
  1. $x_1\le3$ and $x_2\le2$, i.e., $x_j\le\lfloor c/w_j\rfloor$
  2. $x_j\le1$
  3. $x_1\le10$ and $x_2\le10$
  4. $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.
dp-f-166 · level facile · notes
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?
  1. Because at most one copy per type is considered
  2. Because the capacity is reduced to $\lfloor c/n\rfloor$
  3. The copies increase the steps to $\Theta(nc^2)$
  4. 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})$).
dp-f-208 · level facile · notes
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?
  1. $121$
  2. $12$
  3. $6$
  4. $4$
Explanation. $\lfloor10/4\rfloor=2$ and $\lfloor10/3\rfloor=3$: $(2+1)(3+1)=12$ candidates, only some of which respect the capacity.
dp-f-209 · level facile · notes
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?
  1. $(2,1)$, weight $10$, profit $17$
  2. $(3,1)$, weight $13$, profit $22$
  3. $(1,2)$, weight $11$, profit $19$
  4. $(0,3)$, weight $12$, profit $21$
Explanation. $2\cdot3+1\cdot4=10\le c$ and $2\cdot5+7=17$; the others exceed the capacity.
dp-f-210 · level facile · notes
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?
  1. Because in the UKP at most one copy is taken
  2. Because the copies have different weights
  3. Because the capacity is unlimited
  4. 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.
dp-f-211 · level facile · notes
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?
  1. About $2^{10}$; exponential
  2. About $12$; $\Theta(n+c)$
  3. About $20$; $\Theta(nc)$
  4. 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.
dp-f-212 · level facile · notes
The first DP for the unbounded knapsack uses a single vector $v(0),\dots,v(c)$. Which recursion does it compute, with $v(0)=0$?
  1. $v(k)=\min_j\{w_j+v(k-p_j)\}$
  2. $v(k)=\max\{v(k-1),\ \max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}\}$
  3. $v(k)=\max_j\{p_j+v(k-w_j)\}$ with at most one copy per type
  4. $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.
dp-f-213 · level facile · notes
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?
  1. 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
  2. The rows are used in reverse order
  3. The number of steps becomes $\Theta(nc^2)$
  4. 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.
dp-f-214 · level facile · notes
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?
  1. It stays the same
  2. It becomes $100$ times larger
  3. It grows by a single step
  4. 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.
dp-f-265 · level ipotesi · notes
In the unbounded knapsack (UKP) the DP uses a single index: $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$. Which feature of the problem allows this?
  1. Unlimited copies of each type
  2. Weights sorted in increasing order
  3. At most one copy per type
  4. Capacity filled exactly
Explanation. With unlimited copies the possible choices depend only on the residual capacity, not on the items already used.
dp-f-266 · level ipotesi · notes
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?
  1. The profits are positive
  2. The weights exceed $c$
  3. Each type appears at least once
  4. 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.
dp-f-267 · level teorema · notes
The second DP algorithm for the unbounded knapsack uses $v(j,k)=\max\{v(j-1,k),\,p_j+v(j,k-w_j)\}$. Why is the second term in row $j$?
  1. To use type $j$ only once
  2. Because $v$ does not depend on $j$
  3. After a copy of type $j$ more copies can be taken
  4. Row $j-1$ is not computed yet
Explanation. Staying in row $j$ keeps type $j$ available: this is the difference with the 0/1 knapsack.
dp-f-268 · level teorema · notes
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?
  1. $\Theta(2^n c)$, exponential
  2. $\Theta(nc)$, pseudo-polynomial
  3. $\Theta(nc)$, polynomial
  4. $\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.

4. DP for the bounded knapsack problem (22)

dp-f-010 · level facile · notes
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?
  1. $11$ ($d=0,\dots,10$)
  2. $3$ ($d=0,1,2$)
  3. $4$ ($d=0,1,2,3$)
  4. $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.
dp-f-011 · level facile · notes
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?
  1. 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
  2. It generalizes the KP ($b_j=1$) but not the UKP; the DP executes $\Theta(nc\,b_{\max})$ steps
  3. It generalizes the KP ($b_j=1$) and the UKP ($b_j=\lfloor c/w_j\rfloor$); the DP executes $\Theta(nc)$ steps
  4. 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.
dp-f-012 · level facile · notes
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?
  1. $k\leftarrow k-s[j][k]$, and $j$ decreases by $1$
  2. $k\leftarrow k-w_j$, and $j$ stays the same
  3. $k$ stays the same, and $j$ decreases by $s[j][k]$
  4. $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.
dp-f-067 · level facile · notes
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?
  1. $144$
  2. $64$
  3. $8$
  4. $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.
dp-f-068 · level facile · notes
In the bounded knapsack (BKP: profits $p_j$, weights $w_j$, available copies $b_j$, capacity $c$), how is a feasible solution encoded?
  1. By a subset of the items of total weight at most $c$
  2. By an integer vector $x\ge 0$ with $\sum_j w_jx_j=c$
  3. By a binary vector $x$ with $\sum_j b_jw_jx_j\le c$
  4. 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$).
dp-f-069 · level facile · notes
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)$?
  1. $11$
  2. $16$
  3. $15$
  4. $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$.
dp-f-070 · level facile · notes
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?
  1. $n$, one for every item type
  2. $\min\{b_j,\lfloor k/w_j\rfloor\}+1$, one for every number of copies of type $j$
  3. $2$, as in the KP
  4. $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.
dp-f-071 · level facile · notes
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?
  1. It is non-decreasing in $k$: with more capacity there are more feasible solutions
  2. It is strictly increasing in $k$
  3. It is constant: the profit does not depend on the capacity
  4. 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.
dp-f-072 · level facile · notes
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$?
  1. $-\infty$ for $k\ge 1$
  2. $k$ for every $k$
  3. $+\infty$ for $k\ge 1$
  4. $0$ for every $k$
Explanation. With no type available the only solution is the empty knapsack, feasible for every capacity and with profit $0$.
dp-f-073 · level facile · notes
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$?
  1. $\Theta(2^{\sum_j b_j})$, exponential
  2. $\Theta(c\,b_{\max})$, independent of $n$
  3. $\Theta(c\sum_j b_j)$, at most $\Theta(nc\,b_{\max})$ as the direct DP
  4. $\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.
dp-f-074 · level facile · notes
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?
  1. When $b_jw_j<c$
  2. When $b_j\ge\lfloor c/w_j\rfloor$: more copies would not fit anyway
  3. When $b_j=1$
  4. 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.
dp-f-075 · level facile · notes
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?
  1. To the 0-1 knapsack DP: $v(j,k)=\max\{v(j-1,k),\ p_j+v(j-1,k-w_j)\}$
  2. To the unbounded knapsack DP: $v(j,k)=\max\{v(j-1,k),\ p_j+v(j,k-w_j)\}$
  3. To the subset sum DP, with boolean values
  4. 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.
dp-f-167 · level facile · notes
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)?
  1. $30$
  2. $128$
  3. $7$
  4. $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.
dp-f-168 · level ipotesi · notes
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?
  1. Because in the BKP always $b_j=1$
  2. Because the DP ignores the types with $b_j>c$
  3. It cannot: $b_{\max}$ may exceed $c$ and the bound grows
  4. 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)$.
dp-f-215 · level facile · notes
Bounded knapsack with $c=12$, weights $w=(5,3,2)$ and bounds $b=(1,2,4)$ on the copies. Which vector $(x_1,x_2,x_3)$ is a feasible solution?
  1. $(1,1,2)$
  2. $(0,2,4)$
  3. $(1,3,0)$
  4. $(2,0,1)$
Explanation. $(1,1,2)$ weighs $5+3+4=12$ and respects the bounds. $(0,2,4)$ weighs $14$; $(1,3,0)$ exceeds $b_2=2$; $(2,0,1)$ exceeds $b_1=1$.
dp-f-216 · level facile · notes
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?
  1. $3$
  2. $8$
  3. $30$
  4. $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.
dp-f-217 · level facile · notes
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?
  1. $3$
  2. $8$
  3. $4$
  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})$.
dp-f-218 · level facile · notes
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$?
  1. $44$
  2. $134$
  3. $90$
  4. $120$
Explanation. $3\cdot2\cdot5\cdot3=90$, $3\cdot2\cdot5=30$, then $2+8+4$: overall $134$. $90$ is only the dominant term.
dp-f-269 · level teorema · notes
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?
  1. $\Theta(n\,b_{\max})$
  2. $\Theta(c\,b_{\max}^{\,n})$
  3. $\Theta(nc\,b_{\max})$
  4. $\Theta(nc)$
Explanation. $(n+1)(c+1)$ cells, each with up to $b_{\max}+1$ comparisons.
dp-f-270 · level ipotesi · notes
In the bounded knapsack $b_j$ can be replaced by $\min\{b_j,\lfloor c/w_j\rfloor\}$. Why does the problem not change?
  1. All $b_j$ become $1$
  2. More than $\lfloor c/w_j\rfloor$ copies never fit anyway
  3. The optimum uses fewer than $b_j/2$ copies
  4. Types with $b_j>c$ are removed
Explanation. Each copy weighs $w_j$: with capacity $c$ at most $\lfloor c/w_j\rfloor$ fit; moreover $b_{\max}\le c$.
dp-f-271 · level teorema · notes
The bounded knapsack (BKP), with at most $b_j$ copies of type $j$, generalizes which problems?
  1. The 0/1 knapsack ($b_j=1$) and the unbounded knapsack ($b_j=\lfloor c/w_j\rfloor$)
  2. The 0/1 knapsack ($b_j=0$) and subset sum ($b_j=1$)
  3. The unbounded knapsack ($b_j=1$) and the 0/1 knapsack ($b_j=c$)
  4. Coin change ($b_j=1$) and the 0/1 knapsack ($b_j=c$)
Explanation. One copy per type gives the 0/1 knapsack; all copies that fit give the unbounded knapsack.
dp-f-272 · level ipotesi · notes
In the recurrence $v(j,k)=\max_{d}\{d\,p_j+v(j-1,k-d\,w_j)\}$ of the bounded knapsack, which values does the number $d$ of copies take?
  1. $0,1,\dots,b_j$, whatever $k$ is
  2. $1,2,\dots,\lfloor c/w_j\rfloor$
  3. Only $0$ or $b_j$
  4. $0,1,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}$
Explanation. At most $b_j$ copies, and they must fit the residual capacity: $d\,w_j\le k$.

5. DP for the subset sum problem (18)

dp-f-013 · level facile · notes
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?
  1. $r(j,0)=\textit{true}$ for every $j$, and $r(0,k)=\textit{false}$ for $k\ge 1$
  2. $r(j,0)=\textit{false}$ for every $j$, and $r(0,k)=\textit{true}$ for $k\ge 1$
  3. $r(0,k)=\textit{true}$ for every $k$
  4. $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.
dp-f-014 · level facile · notes
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?
  1. In cell $r(c,n)$
  2. In any true cell of column $c$
  3. In the last true cell of row $n$
  4. 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.
dp-f-015 · level facile · notes
In subset sum (integers $w_1,\dots,w_n$, target $c$: does some subset sum to exactly $c$?), how many steps does the DP with table $r(j,k)$ execute?
  1. $\Theta(2^n)$
  2. $\Theta(n\log c)$
  3. $\Theta(nc)$
  4. $\Theta(c^2)$
Explanation. The table has $(n+1)(c+1)$ cells, each computed in constant time: $\Theta(nc)$, a pseudo-polynomial time.
dp-f-076 · level facile · notes
Subset sum: weights $w=(3,5,7)$, target $c=10$. $r(j,k)$ is true if a subset of the first $j$ weights sums to exactly $k$. What is $r(3,10)$?
  1. False, because $10$ is not a weight
  2. True, for example $3+7$
  3. False: no subset sums to $10$
  4. True, because $10\le 3+5+7$
Explanation. The reachable sums are $0,3,5,7,8,10,12,15$: $10=3+7$. That $c$ is below the total sum is not enough: an exact sum is needed.
dp-f-077 · level facile · notes
Subset sum with weights $w=(2,2,2)$ and target $c=5$: $r(j,k)$ is true if a subset of the first $j$ weights sums to exactly $k$. What is $r(3,5)$?
  1. False: the reachable sums are $0,2,4,6$
  2. True: $5\le 6$
  3. True: $2+2+1$
  4. False: the table has no column $5$
Explanation. With all weights even every sum is even, so $5$ is not reachable. Column $5$ exists ($k=0,\dots,c$) and contains only false values.
dp-f-078 · level facile · notes
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?
  1. The choice of not using weight $w_j$
  2. The choice of using weight $w_j$ twice
  3. The check that $k$ does not exceed the target $c$
  4. 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.
dp-f-079 · level facile · notes
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)$?
  1. If $r(j-1,k)$ is true take $w_j$; otherwise exclude it
  2. Take the largest weight and restart with $c-w_{\max}$
  3. 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$
  4. 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$.
dp-f-080 · level facile · notes
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?
  1. $13$
  2. $10$
  3. $12$
  4. $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.
dp-f-081 · level facile · notes
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?
  1. From $c$ down to $w_j$, decreasing, so as not to use the same weight twice
  2. From $w_j$ up to $c$, increasing, to read already updated cells
  3. In any order, because the operation is an «or»
  4. 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.
dp-f-082 · level facile · notes
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$?
  1. $100$
  2. $105$
  3. $32$
  4. $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$.
dp-f-083 · level facile · notes
The DP for subset sum takes $\Theta(nc)$ steps with $n$ weights and target $c$. Why does subset sum remain NP-complete?
  1. Because the number of subsets is $2^n$, and the DP lists them all
  2. Because the table has boolean values instead of integers
  3. $c$ is written with about $\log_2 c$ digits, and $\Theta(nc)$ is exponential in that number of digits
  4. 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.
dp-f-084 · level facile · notes
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?
  1. It is yes if and only if $v(n,c)=\sum_j w_j$
  2. It is yes if and only if $v(n,c)=c$
  3. It is yes if and only if $v(n,c)\ge 1$
  4. 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.
dp-f-169 · level facile · notes
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?
  1. $\Theta(nc)$, as the 0/1 knapsack DP
  2. $\Theta(2^n)$
  3. $\Theta(n\log c)$
  4. $\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.
dp-f-219 · level facile · notes
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?
  1. $44$
  2. $16$
  3. $55$
  4. $40$
Explanation. $(4+1)(10+1)=55$ cells, each computed in constant time: $\Theta(nc)$.
dp-f-220 · level facile · notes
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?
  1. $\Theta(2^n)$
  2. $\Theta(n)$: one step per item
  3. $\Theta(nc)$
  4. $\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.
dp-f-273 · level ipotesi · notes
In the DP for subset sum, $r(j,k)$ tells whether $k$ is the weight of a subset of the first $j$ items. Why is $r(j,0)=\textit{true}$ for every $j$?
  1. The empty subset weighs $0$
  2. The weights are positive
  3. $0$ is the target value
  4. The first item weighs $0$
Explanation. The value $0$ is always reached with no item; with no item no $k\ge 1$ is reached.
dp-f-274 · level teorema · notes
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»?
  1. If and only if $z\ge c/2$
  2. If and only if $z<c$
  3. Never: the problems are unrelated
  4. 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$.
dp-f-275 · level teorema · notes
The DP $r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)$ for subset sum with $n$ items and target value $c$: how many steps, and where is the answer read?
  1. $\Theta(2^n)$; in $r(n,c)$
  2. $\Theta(n+c)$; in $r(n,0)$
  3. $\Theta(nc)$; in $r(n,c)$
  4. $\Theta(nc)$; in $r(c,n)$
Explanation. $(n+1)(c+1)$ cells with one logical «or» each; the answer concerns all items and the value $c$.

6. DP for the multiple-choice knapsack problem (16)

dp-f-016 · level facile · notes
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?
  1. $v(0,k)=0$ for every $k$; without feasible solutions it is $0$
  2. $v(0,k)=-\infty$ for $k\ge 1$; without feasible solutions it is $0$
  3. $v(0,k)=k$ for every $k$; without feasible solutions it is $+\infty$
  4. $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.
dp-f-017 · level facile · notes
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?
  1. The base case $v(0,k)$, because the first class replaces it
  2. The check $w_j\le k$, because the class fixes the weight
  3. The term $v(h-1,k)$, because every class gives exactly one item
  4. 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.
dp-f-018 · level facile · notes
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?
  1. $\Theta(2^q c)$
  2. $\Theta\big(c\sum_{h=1}^{q}|\mathscr{J}_h|\big)=\Theta(nc)$
  3. $\Theta(qc)$
  4. $\Theta(n^q c)$
Explanation. For every class $h$ and every capacity $k$ the items of the class are tried: in total $c\sum_h|\mathscr{J}_h|=\Theta(nc)$.
dp-f-121 · level facile · notes
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)$?
  1. $7$
  2. $10$
  3. $9$
  4. $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.
dp-f-122 · level facile · notes
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$?
  1. The profit of the lightest item of class $2$
  2. $v(2,2)=-\infty$: there is no feasible solution
  3. $v(2,2)=0$: no item is chosen
  4. 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.
dp-f-123 · level facile · notes
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?
  1. $|\mathscr{J}_h|$, one per item of class $h$ that fits
  2. $2$, as in the 0/1 KP
  3. $|\mathscr{J}_h|+1$, counting the choice of no item
  4. $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.
dp-f-124 · level facile · notes
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)$?
  1. Choose $s(q,c)$ and repeat it for every class
  2. Choose in every class the item of largest profit
  3. Choose $j=s(h,k)$ and set $h\leftarrow h-1$ without changing $k$
  4. 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.
dp-f-125 · level facile · notes
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$?
  1. $96$
  2. $45$
  3. $64$
  4. $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)$.
dp-f-126 · level facile · notes
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$?
  1. $0$
  2. $3$
  3. $5$
  4. $-\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.
dp-f-127 · level facile · notes
How is a 0-1 knapsack (KP) with $n$ items written as a multiple-choice knapsack (MCKP), where exactly one item per class is chosen?
  1. One class per item, with the item and a dummy item of zero profit and weight
  2. A single class with all the $n$ items
  3. Two classes, the even and the odd items
  4. It cannot: in the MCKP every class gives exactly one item
Explanation. Choosing the dummy item means excluding the real one: the $2$ choices per class are the $2$ decisions of the KP.
dp-f-128 · level facile · notes
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$?
  1. $-\infty$ for every $k\ge 1$
  2. $-\infty$ for $k=0$ and $0$ otherwise
  3. $k$ for every $k$
  4. $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.
dp-f-129 · level facile · notes
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?
  1. It changes, unless the classes are sorted by profit
  2. It does not change, but the DP becomes incorrect
  3. It does not change: only the intermediate values of the table change
  4. 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.
dp-f-170 · level facile · notes
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?
  1. $2^{12}$ times a constant
  2. $12\cdot50=600$ times a constant
  3. $4\cdot2\cdot6\cdot50=2400$ times a constant
  4. $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.
dp-f-221 · level facile · notes
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?
  1. $\Theta(qc)$
  2. $\Theta(2^q)$
  3. $\Theta(q)$: one step per class
  4. $\Theta(n)$: one step per item
Explanation. Going back from capacity $c$ one reads, class by class, the chosen item: one step per class.
dp-f-276 · level ipotesi · notes
In the DP for the multiple-choice knapsack (MCKP) $v(h,k)=-\infty$ when no item of class $h$ fits. Which constraint of the problem is this based on?
  1. At most one item is chosen from each class
  2. The items are in unlimited copies
  3. The capacity must be filled exactly
  4. Exactly one item is chosen from each class
Explanation. If a class cannot contribute an item, the subproblem has no feasible solution: $-\infty$.
dp-f-277 · level teorema · notes
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?
  1. $\Theta(nc)$; if $v(q,c)=0$
  2. $\Theta(n^2c)$; if $v(q,0)=-\infty$
  3. $\Theta(nc)$; if $v(q,c)=-\infty$
  4. $\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)

dp-f-019 · level facile · notes
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)$?
  1. $50$
  2. $150$
  3. $120$
  4. $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\}$.
dp-f-020 · level facile · notes
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}$?
  1. When $w_{dj}\le k_d$ for every dimension $d$
  2. When $w_{dj}\le k_d$ for at least one dimension $d$
  3. When $\sum_d w_{dj}\le\sum_d k_d$
  4. 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.
dp-f-021 · level facile · notes
In the multidimensional knapsack problem (MDKP) with $m$ dimensions and capacities $c_1,\dots,c_m$, why does the DP become impractical as $m$ grows?
  1. The number of states contains the sum $\sum_d(c_d+1)$, exponential in $m$
  2. The recurrence loses optimal substructure as soon as $m\ge 2$
  3. The subproblems stop overlapping as soon as $m\ge 2$
  4. The number of states contains the product $\prod_d(c_d+1)$, exponential in $m$
Explanation. This is the curse of dimensionality: every dimension multiplies the number of states by $c_d+1$.
dp-f-130 · level facile · notes
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))$?
  1. $5$
  2. $7$
  3. $9$
  4. $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\}$.
dp-f-131 · level facile · notes
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?
  1. $v(j,\vet k)=p_j+v(j-1,\vet k-\vet w_j)$ if $\sum_d w_{dj}\le\sum_d k_d$
  2. $v(j,\vet k)=\max\{v(j-1,\vet k),\ p_j+v(j-1,\vet k-\vet w_j)\}$ if $\vet w_j\le\vet k$ componentwise
  3. $v(j,\vet k)=\max\{v(j-1,\vet k),\ p_j+v(j,\vet k-\vet w_j)\}$ if $\vet w_j\le\vet k$
  4. $v(j,\vet k)=\max_d\{v(j-1,k_d),\ p_j+v(j-1,k_d-w_{dj})\}$
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.
dp-f-132 · level facile · notes
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?
  1. $101^{10}$
  2. $10\cdot 101$
  3. $100^{10}$
  4. $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$.
dp-f-133 · level facile · notes
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$?
  1. $-\infty$ for $\vet k\ne\vet 0$
  2. $\sum_d k_d$
  3. $+\infty$ for every $\vet k$
  4. $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.
dp-f-134 · level facile · notes
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?
  1. $j$ stays and $\vet k\leftarrow\vet k-\vet w_j$
  2. $j\leftarrow j-1$ and $\vet k$ stays
  3. $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
  4. $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.
dp-f-135 · level facile · notes
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?
  1. To the multiple knapsack, with a capacity vector
  2. To the 0-1 knapsack, with the DP $v(j,k)$ on a single capacity
  3. To the unbounded knapsack, with the DP $v(k)$
  4. 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$.
dp-f-136 · level facile · notes
In the DP for the multidimensional knapsack (MDKP) with $n$ items and capacities $c_1,\dots,c_m$, how many steps are taken?
  1. $\Theta\big(n\prod_d(c_d+1)\big)$: pseudo-polynomial only for fixed $m$
  2. $\Theta\big(n\sum_d c_d\big)$: pseudo-polynomial for every $m$
  3. $\Theta(nm)$: polynomial
  4. $\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.
dp-f-137 · level facile · notes
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)$?
  1. $75$
  2. $48$
  3. $64$
  4. $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.
dp-f-138 · level facile · notes
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$?
  1. $\Theta(n^2c_1c_2)$, because there are two dimensions
  2. $\Theta(nc_1)$, because the most binding dimension is enough
  3. $\Theta(n\,c_1c_2)$, against $\Theta(nc)$: a second dimension multiplies the work by its capacity
  4. $\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.
dp-f-171 · level facile · notes
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?
  1. $32$
  2. $231$
  3. $30$
  4. $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.
dp-f-172 · level ipotesi · notes
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?
  1. If the number $m$ of dimensions is fixed: then it is $\Theta(n\prod_dc_d)$, polynomial in the values of the capacities
  2. Always, for every $m$
  3. Only if all capacities are equal
  4. 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.
dp-f-222 · level facile · notes
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?
  1. $11$
  2. $100$
  3. $1024$
  4. $20$
Explanation. $2^{10}=1024$: even with minimal capacities the number of states grows exponentially with the dimensions. It is the curse of dimensionality.
dp-f-278 · level teorema · notes
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?
  1. The time becomes polynomial
  2. The number of states does not change
  3. The states grow exponentially in $m$
  4. The time grows linearly in $m$
Explanation. The product of the $m$ capacities explodes: the curse of dimensionality.
dp-f-279 · level ipotesi · notes
Under which hypothesis is the DP for the multidimensional knapsack, with $\Theta(m\,n\prod_d(c_d+1))$ steps, pseudo-polynomial?
  1. $n\le m$
  2. The number $m$ of dimensions is fixed
  3. All capacities $c_d$ are equal
  4. The profits are integer
Explanation. With a constant $m$ the time is $\Theta(n\prod_d c_d)$, polynomial in the capacity values; with $m$ in the input it is exponential.

8. DP for the knapsack problem with setups (17)

dp-f-022 · level facile · notes
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?
  1. Once, in the row $u(h,0,k)=v(h-1,k-s_h)-f_h$
  2. Once for every chosen item of the class, subtracting $f_h$ and $s_h$
  3. Once, in the row $v(h,k)$, if $v(h,k)>v(h-1,k)$
  4. 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.
dp-f-023 · level facile · notes
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$?
  1. $v(h,k)=v(h-1,k)+u(h,t_h,k)$
  2. $v(h,k)=\max\{v(h-1,k),\ u(h,0,k)\}$
  3. $v(h,k)=u(h,t_h,k)$
  4. $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)$).
dp-f-024 · level facile · notes
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?
  1. Because $v(h-1,k)$ is not yet computed at that point
  2. Because $v(h-1,k)$ equals $-\infty$ when $s_h>0$
  3. Because items of the class would be chosen without paying its setup
  4. 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.
dp-f-139 · level facile · notes
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?
  1. $5$
  2. $6$
  3. $0$
  4. $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.
dp-f-140 · level facile · notes
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$?
  1. $-f_h$: the setup is paid without capacity
  2. $v(h-1,k)$: the setup is ignored
  3. $-\infty$: the class cannot be opened because the setup weight does not fit
  4. $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.
dp-f-141 · level facile · notes
In the DP for the knapsack with setups (KPS), $v(h,k)$ is the optimal value with classes $1,\dots,h$ and capacity $k$. What is the base case $v(0,k)$?
  1. $k$ for every $k$
  2. $0$ for every $k$
  3. $-\infty$ for $k\ge 1$
  4. $-\sum_h f_h$
Explanation. With no classes the empty solution is feasible and pays no setup: it is worth $0$ for every capacity.
dp-f-142 · level facile · notes
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)\}$?
  1. Because $v(h-1,k-s_h)-f_h\le v(h-1,k)$: the setup is paid and capacity lost with no gain
  2. Because $u(h,0,k)$ is always $-\infty$
  3. Because class $h$ has at least one item with positive profit
  4. 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.
dp-f-143 · level facile · notes
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?
  1. $\Theta(nqc)$
  2. $\Theta(2^qnc)$
  3. $\Theta(nc^2)$
  4. $\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.
dp-f-144 · level facile · notes
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$?
  1. How many classes to open in total
  2. Whether the setup weight $s_h$ exceeds the total capacity $c$
  3. Whether class $h$ is open, comparing $v(h,k)$ with $v(h-1,k)$
  4. 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.
dp-f-145 · level facile · notes
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?
  1. When the class has a single item
  2. When $f_h\ge P_h$: even taking all the items the net gain is not positive
  3. When $f_h\le P_h$
  4. 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.
dp-f-146 · level facile · notes
What does the knapsack with setups (KPS) reduce to when all setup costs and weights are zero ($f_h=s_h=0$)?
  1. To the 0-1 knapsack on the same items
  2. To the multiple-choice knapsack, one item per class
  3. To the unbounded knapsack
  4. To the multiple knapsack, one knapsack per class
Explanation. Opening a class costs nothing, so the classes do not matter: the items remain, each chosen at most once, with a single capacity.
dp-f-147 · level facile · notes
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?
  1. $u(h,i,k)=\max\{v(h-1,k),\ p_j+v(h-1,k-w_j)\}$
  2. $u(h,i,k)=p_j-f_h+u(h,i-1,k-w_j-s_h)$
  3. $u(h,i,k)=\max\{u(h,i-1,k),\ p_j+u(h,i,k-w_j)\}$
  4. $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.
dp-f-173 · level facile · notes
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?
  1. Nothing: the setups are ignored
  2. A number of rows proportional to $q$ (opening and closing every class), absorbed by $\Theta(nc)$ since $q\le n$
  3. A factor $2^q$ for the activated classes
  4. 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)$.
dp-f-223 · level facile · notes
The DP for the knapsack with setups performs $S(n,q,c)=4n(c+1)+8q(c+1)+2n+q+2c+4$ steps. How many are they with $n=4$ items, $q=2$ classes and $c=5$?
  1. $96$
  2. $192$
  3. $120$
  4. $216$
Explanation. $4\cdot4\cdot6=96$, $8\cdot2\cdot6=96$, then $8+2+10+4$: $216$. The setup rows count as much as the item rows, but remain $\Theta(nc)$.
dp-f-224 · level facile · notes
After computing the table of the DP for the knapsack with setups, how many steps does the reconstruction of the chosen items and classes need?
  1. $\Theta(q)$
  2. $\Theta(c)$
  3. $\Theta(n)$
  4. $\Theta(nc)$
Explanation. One goes back through the table row by row, with one step per item and per setup row: $\Theta(n+q)=\Theta(n)$.
dp-f-280 · level ipotesi · notes
In the DP for the knapsack with setups class $h$ opens with $u(h,0,k)=v(h-1,k-s_h)-f_h$. What does this initial value guarantee?
  1. Class $h$ always stays closed
  2. The setup takes no capacity
  3. The setup (weight $s_h$, cost $f_h$) is paid once per class
  4. The setup is paid for every item of the class
Explanation. Setup cost and weight are subtracted when the class opens; then the KP recurrence continues over its items.
dp-f-281 · level teorema · notes
How many steps does the DP for the knapsack with setups with $n$ items and capacity $c$ execute?
  1. $\Theta(nc^2)$
  2. $\Theta(nc)$
  3. $\Theta(n^2c)$
  4. $\Theta(2^q nc)$
Explanation. As the DP of the 0/1 knapsack: a constant number of comparisons per item and capacity, plus those of the classes.

9. DP for the multiple knapsack problem (19)

dp-f-025 · level facile · notes
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?
  1. All the components decrease, by $w_j$
  2. All the components decrease, by $w_j/m$
  3. It does not change: capacities are checked at the end
  4. 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.
dp-f-026 · level facile · notes
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?
  1. $2$: item $j$ is chosen or not, regardless of the knapsack
  2. $m$: item $j$ always goes into one of the knapsacks where it fits
  3. $m+1$: item $j$ stays out or goes into one of the knapsacks where it fits
  4. $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$.
dp-f-027 · level facile · notes
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?
  1. The value of a feasible solution of the MKP
  2. An upper bound: the solution may not be divisible among the knapsacks
  3. A lower bound: the solution can always be divided among the knapsacks
  4. 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.
dp-f-148 · level facile · notes
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?
  1. $9$
  2. $8$
  3. $13$
  4. $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.
dp-f-149 · level facile · notes
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?
  1. $v(j,\vet k)=\max\{v(j-1,\vet k),\ p_j+v(j-1,\vet k-w_j\vet 1)\}$
  2. $v(j,\vet k)=\max_i\{p_j+v(j-1,\vet k-w_j\vet e_i)\}$
  3. $v(j,\vet k)=\max\{v(j-1,\vet k),\ p_j+v(j,\vet k-w_j\vet e_1)\}$
  4. $v(j,\vet k)=\max\{v(j-1,\vet k),\ \max_{i:\,w_j\le k_i}\{p_j+v(j-1,\vet k-w_j\vet e_i)\}\}$
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.
dp-f-150 · level facile · notes
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?
  1. Removing empty knapsacks from the state
  2. It cannot: the DP must distinguish the knapsacks
  3. Keeping only sorted vectors, for example with non-increasing components
  4. 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$.
dp-f-151 · level facile · notes
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?
  1. As $2^n$, independently of $m$
  2. As $(c+1)^m$ per item: exponentially in $m$
  3. As $m(c+1)$: linearly in $m$
  4. 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.
dp-f-152 · level facile · notes
In the DP for the multiple knapsack (MKP), what is the base case $v(0,\vet k)$, with no items and residual capacities $\vet k$?
  1. $0$ for every $\vet k$
  2. $-\infty$ if some $k_i>0$
  3. $\sum_i k_i$
  4. $+\infty$ for every $\vet k$
Explanation. With no items all knapsacks stay empty, a feasible solution of value $0$ for every capacity vector.
dp-f-153 · level facile · notes
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?
  1. Only whether item $j$ is chosen or not
  2. The total profit of the fullest knapsack
  3. The vector $\vet k$ of the next state
  4. 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.
dp-f-154 · level facile · notes
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$?
  1. To the multidimensional knapsack with one dimension per item
  2. To bin packing with one bin
  3. To the 0-1 knapsack with capacity $c_1$
  4. 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$.
dp-f-155 · level facile · notes
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)$?
  1. $40$
  2. $120$
  3. $96$
  4. $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.
dp-f-156 · level facile · notes
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$?
  1. $\Theta\big(nm\prod_i(c_i+1)\big)$
  2. $\Theta\big(n\sum_i c_i\big)$
  3. $\Theta\big(n(m+1)\big)$
  4. $\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$.
dp-f-174 · level facile · notes
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?
  1. $35$
  2. $12$
  3. $48$
  4. $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.
dp-f-225 · level facile · notes
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?
  1. $72$
  2. $96$
  3. $60$
  4. $112$
Explanation. $N=2\cdot3=6$: $3\cdot2\cdot2\cdot6=72$, $2\cdot2\cdot6=24$, $2\cdot6=12$, then $2+2$: $112$.
dp-f-226 · level facile · notes
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?
  1. $7$
  2. $8$
  3. $27$
  4. $9$
Explanation. $(2+1)^3=27$: one residual capacity value per knapsack, combined in all ways.
dp-f-227 · level facile · notes
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$)?
  1. $13$ and $39$
  2. $13$ and $125$
  3. $13$ and $15$
  4. $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.
dp-f-228 · level teorema · notes
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?
  1. For fixed $m$ the product is a polynomial of degree $m$ in the capacities; with variable $m$ the exponent grows with the instance
  2. Because for fixed $m$ the problem is in P
  3. Because the number of items does not count
  4. 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.
dp-f-282 · level teorema · notes
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?
  1. $m$; $\Theta(n\,m^2)$
  2. $2^m$; $\Theta(n\sum_i c_i)$
  3. $m+1$; $\Theta(m\,n\prod_i(c_i+1))$
  4. $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.
dp-f-283 · level ipotesi · notes
For the multiple knapsack, why is it not enough to fill one knapsack at a time with the 0/1 knapsack DP on the remaining items?
  1. Because the items are in unlimited copies
  2. The choices of a knapsack depend on the others: the optimum can be lost
  3. Because the 0/1 knapsack DP is not exact
  4. Because the capacities must be equal
Explanation. An optimal filling of the first knapsack may take items needed by the others: the DP must consider all capacities together.

10. DP for the uncapacitated lot sizing problem (31)

dp-f-028 · level teorema · notes
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?
  1. Every ULS instance has an optimal solution with $s_t\,x_t=0$ for every period $t$
  2. Every ULS instance has an optimal solution with $s_{t-1}\,x_t=0$ for every period $t$
  3. Every optimal solution of the ULS has $s_{t-1}\,x_t=0$ for every period $t$
  4. 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.
dp-f-029 · level ipotesi · notes
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?
  1. Non-negative costs and unlimited production, to move production between two periods without increasing the cost
  2. Non-negative costs and constant capacities, to move production between two periods without increasing the cost
  3. Zero holding costs and unlimited production, so that inventory never costs anything
  4. 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.
dp-f-030 · level facile · notes
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?
  1. $\Theta(m^3)$
  2. $\Theta(2^m)$
  3. $\Theta(m\,D_{1,m})$
  4. $\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)$.
dp-f-103 · level facile · notes
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}$?
  1. $130$
  2. $160$
  3. $180$
  4. $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.
dp-f-104 · level facile · notes
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?
  1. $c_{j,t}=c_{j,t-1}\cdot d_t$
  2. $c_{j,t}=c_{j,t-1}+\big(vc_j+\sum_{k=j}^{t-1}hc_k\big)\,d_t$
  3. $c_{j,t}=c_{j,t-1}+sc_j+vc_j\,d_t$
  4. $c_{j,t}=c_{j,t-1}+hc_t\,d_t$
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)$.
dp-f-105 · level facile · notes
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$?
  1. $15$
  2. $25$
  3. $10$
  4. $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.
dp-f-106 · level facile · notes
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)$?
  1. $220$
  2. $230$
  3. $300$
  4. $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$.
dp-f-107 · level facile · notes
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$?
  1. Record a run in every period $t$ with $v(t)<v(t-1)$
  2. Record the runs in $j^*(1),j^*(2),\dots,j^*(m)$, forwards
  3. Record a run in $j^*(t)$ and set $t\leftarrow j^*(t)-1$, until $t=0$
  4. 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$.
dp-f-108 · level facile · notes
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?
  1. The quantity produced in period $t$
  2. The period of the last run, which produces the demands of periods $j,\dots,t$
  3. The period of the first run, which produces the demands of periods $1,\dots,j$
  4. 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$.
dp-f-109 · level facile · notes
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$?
  1. $32$
  2. $64$
  3. $21$
  4. $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.
dp-f-110 · level facile · notes
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?
  1. Exactly the demand $d_j$ of its own period
  2. The total demand $D_{1,m}$ of all periods
  3. Any quantity, as long as the stock stays non-negative
  4. 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.
dp-f-111 · level facile · notes
In the Wagner–Whitin algorithm for uncapacitated lot sizing, $v(t)$ is the optimal cost of periods $1,\dots,t$. Why is the base case $v(0)=0$?
  1. Because the initial stock equals the demand of period $1$
  2. Because $v(0)$ is never read by the recurrence
  3. An empty set of periods has no demand and no cost
  4. Because the first period has no setup cost
Explanation. $v(0)$ is read by the term $j=1$: $v(t)=v(0)+c_{1,t}$ is the plan with a single run in period $1$, and its cost is exactly $c_{1,t}$.
dp-f-175 · level facile · notes
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}$?
  1. $40$
  2. $110$
  3. $80$
  4. $70$
Explanation. $D_{2,4}=d_2+d_3+d_4=10+30+40=80$. $70$ forgets $d_2$; $110$ is the total demand.
dp-f-176 · level facile · notes
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?
  1. $(30,0,70,0,20)$
  2. $(30,0,70,0,10)$
  3. $(10,20,30,40,10)$
  4. $(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$.
dp-f-177 · level facile · notes
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}$?
  1. $120$
  2. $110$
  3. $90$
  4. $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.
dp-f-178 · level teorema · notes
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}$?
  1. Because every unit stays in stock a single period
  2. Because the demand of the periods from $j$ to $k$ is kept in stock
  3. Because the holding cost is paid only in the setup period
  4. 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.
dp-f-179 · level facile · notes
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?
  1. $\Theta(m)$: one term per period
  2. $\Theta(m\,D_{1,m})$: pseudo-polynomial in the demand
  3. $\Theta(m^2)$: one pair $(j,t)$ with $j\le t$ for every term of the minimum
  4. $\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.
dp-f-229 · level facile · notes
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?
  1. $x_t\le D_{t,m}\,y_t$, with $D_{t,m}$ the demand of the periods from $t$ to $m$
  2. $s_{t-1}+x_t=d_t+s_t$
  3. $y_t\le x_t$
  4. $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.
dp-f-230 · level facile · notes
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?
  1. $110$
  2. $50$
  3. $360$
  4. $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.
dp-f-231 · level facile · notes
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}$?
  1. Yes: $(40,30,0,50,0)$
  2. No: $s_3<0$
  3. Yes: $(40,30,0,10,0)$
  4. 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.
dp-f-232 · level facile · notes
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?
  1. $120$
  2. $16$
  3. $32$
  4. $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.
dp-f-233 · level facile · notes
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}$?
  1. $90$
  2. $70$
  3. $120$
  4. $50$
Explanation. $50+hc_3D_{4,4}=50+40=90$: the demand of period $4$ stays in stock one period.
dp-f-234 · level facile · notes
In the Wagner-Whitin algorithm, besides computing the cost matrix, the number of steps is $3+3m+3\sum_{t=1}^mt$. What is it for $m=4$?
  1. $30$
  2. $27$
  3. $63$
  4. $45$
Explanation. $3+12+3\cdot10=45$. The term $\sum_tt=m(m+1)/2$ gives the order $\Theta(m^2)$.
dp-f-235 · level facile · notes
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?
  1. $10$
  2. $32$
  3. $15$
  4. $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.
dp-f-284 · level teorema · notes
What does the zero-inventory ordering property (Wagner and Whitin) state for uncapacitated lot sizing (ULS), with productions $x_t$ and inventories $s_t$?
  1. Every feasible solution has $x_t=d_t$
  2. Some optimal solution has $s_{t-1}\,x_t=0$ for every $t$
  3. Every optimal solution produces in every period
  4. 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.
dp-f-285 · level ipotesi · notes
Under which hypotheses does the zero-inventory ordering property of lot sizing hold?
  1. No production capacities and non-negative costs
  2. Constant capacities and arbitrary costs
  3. All demands equal
  4. Zero setup costs
Explanation. With unlimited production and non-negative costs it pays to produce only with an empty inventory; with capacities the property fails.
dp-f-286 · level teorema · notes
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?
  1. $\Theta(m)$; a minimum spanning tree
  2. $\Theta(2^m)$; all production plans
  3. $\Theta(m^3)$; a maximum flow
  4. $\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$.
dp-f-287 · level ipotesi · notes
In uncapacitated lot sizing, why does a production run covering the periods $j,\dots,t$ produce exactly $D_{j,t}=d_j+\dots+d_t$?
  1. Because the capacity is $D_{j,t}$
  2. Because setup costs are zero
  3. Because of the zero-inventory ordering property
  4. Because the demands are equal
Explanation. Period $j$ produces with an empty inventory and the next run starts empty: exactly the demand of the covered periods is produced.
dp-f-306 · level facile · notes
In uncapacitated lot sizing (ULS) with $m$ periods, demands $d_t$, setup, production and holding costs: what is decided?
  1. Which items to put in the knapsack
  2. In which order to visit the periods
  3. How many machines to use
  4. How much to produce in each period, meeting the demands at minimum cost
Explanation. The solution is the vector of productions $(x_1,\dots,x_m)$; the inventories follow from productions and demands.
dp-f-307 · level facile · notes
In the Wagner–Whitin DP, what does $c_{j,t}$ represent?
  1. The capacity of period $j$
  2. The optimal value of the first $t$ periods
  3. The cost of producing in period $j$ the demand of periods $j,\dots,t$
  4. The total demand of periods $j,\dots,t$
Explanation. It is the cost of a run: setup in $j$, production of $D_{j,t}$ and holding of the units until their period.
dp-f-308 · level facile · notes
In the Wagner–Whitin DP one stores $r[t]$, the period of the last run covering period $t$. What is it for?
  1. To sort the periods
  2. To rebuild backwards an optimal production plan
  3. To compute the total demands
  4. To check the capacities
Explanation. From $t=m$ one reads the period $r[m]$ of the last run, then restarts from $r[m]-1$, down to period $0$.

11. DP for the capacitated lot sizing problem (28)

dp-f-031 · level facile · notes
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?
  1. The period $t$ of the last lot produced, as in the ULS; the optimal value is $v(m)$
  2. The pair $(t,x)$ of the period and the production, with $x\le cap_t$; the optimal value is $v(m,cap_m)$
  3. 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)$
  4. 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.
dp-f-032 · level facile · notes
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$?
  1. $k$: one unit of cost per unit of inventory
  2. $+\infty$: these states are not reachable
  3. $0$: no cost has been paid yet
  4. $-\infty$: these states are not reachable
Explanation. The value $+\infty$ marks the states that cannot be reached; only $v(0,0)=0$.
dp-f-033 · level teorema · notes
In capacitated lot sizing (CLS) over $m$ periods, with total demand $D$ and maximum capacity $C$, which statement on the complexity is correct?
  1. The DP executes $O(mDC)$ steps; with constant capacity it is polynomial, with general capacities NP-hard
  2. The DP executes $O(mDC)$ steps; with constant capacity it is strongly NP-hard
  3. The Wagner-Whitin DP on lots also solves the CLS in $\Theta(m^2)$ steps
  4. 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.
dp-f-112 · level facile · notes
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?
  1. Because the states with larger stock have zero cost
  2. A stock larger than the residual demand would stay unused and violate the zero final stock
  3. Because the capacity of period $t$ is at most $D_{t+1,m}$
  4. 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.
dp-f-113 · level facile · notes
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?
  1. $20$
  2. $22$
  3. $12$
  4. $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.
dp-f-114 · level facile · notes
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?
  1. From all states $(t-1,k')$ with $k'\le k$
  2. Only from state $(t-1,0)$, by the zero-inventory property
  3. From those with $k'=k+d_t$
  4. 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.
dp-f-115 · level facile · notes
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)$?
  1. There are $2^m$ setup choices, each evaluated in $O(DC)$
  2. There are $D\cdot C$ states and $m$ transitions per state
  3. There are at most $m(D+1)$ states $(t,k)$, and each has at most $C+1$ transitions, one per production quantity
  4. 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$.
dp-f-116 · level teorema · notes
Why does the Wagner–Whitin algorithm, which only chooses the periods of the runs, not solve capacitated lot sizing (CLS)?
  1. Because the CLS has a free final stock
  2. With capacities an optimal plan producing only at zero incoming stock may not exist
  3. Because in the CLS the setup costs are zero
  4. 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.
dp-f-117 · level facile · notes
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?
  1. $sc_t$ if $x>0$, plus $vc_t\,x$, plus $hc_t\,k$ for the final stock of period $t$
  2. Always $sc_t$, plus $vc_t\,x$
  3. $sc_t$ if $x>0$, plus $hc_t\,k'$ for the initial stock
  4. 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.
dp-f-118 · level facile · notes
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?
  1. $3$, one for every unit of capacity
  2. $2$: produce or not
  3. $k+1$, one for every smaller stock
  4. $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.
dp-f-119 · level facile · notes
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$?
  1. $v(1,k)=0$ for every $k$, because period $1$ does not produce
  2. $v(1,1)=sc_1+hc_1$, with one unit in stock
  3. $v(1,k)=+\infty$ for every $k$: the demand of period $1$ exceeds its capacity
  4. $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.
dp-f-120 · level facile · notes
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?
  1. The Wagner–Whitin algorithm suffices without changes
  2. The problem is solved in polynomial time
  3. The problem stays strongly NP-hard
  4. 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.
dp-f-180 · level facile · notes
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. $(1,0,0,1,0)$
  2. $(1,0,1,1,0)$
  3. $(1,1,1,1,0)$
  4. $(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.
dp-f-181 · level facile · notes
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}$?
  1. The inventory must be empty at the end of the horizon, so it never exceeds the demand of the following periods
  2. Because the capacity is at most $D_{t+1,m}$
  3. Because the inventory is always zero
  4. 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.
dp-f-182 · level facile · notes
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$?
  1. Because one always produces $d_t$
  2. Because the inventory of the previous period is always $k$
  3. Because the demand is paid in the next period
  4. 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\}\}$.
dp-f-183 · level teorema · notes
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?
  1. Exponential in $m$
  2. Linear in the instance size
  3. Pseudo-polynomial: it is polynomial in the numerical values $D$ and $C$, not in their length in bits
  4. 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.
dp-f-184 · level ipotesi · notes
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?
  1. Every period produces exactly its own demand
  2. 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$
  3. One produces only with empty inventory
  4. 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.
dp-f-236 · level facile · notes
Capacitated lot sizing with demands $d=(2,1,3,4,1)$ and capacity $cap_t=4$ in every period. Which plan is infeasible?
  1. $(4,0,2,4,1)$
  2. $(6,0,0,5,0)$
  3. $(3,0,4,4,0)$
  4. $(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$.
dp-f-237 · level ipotesi · notes
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?
  1. It relies on the zero-inventory property, which fails with capacities: a lot may not fit in the capacity of its period
  2. Because with capacities the setup costs are zero
  3. Because the CLS has a single period
  4. 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).
dp-f-238 · level facile · notes
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?
  1. $55$
  2. $25$
  3. $11$
  4. $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.
dp-f-239 · level facile · notes
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?
  1. From $m^2$ pairs of periods
  2. From $D\cdot C$ pairs of periods
  3. At most $D+1$ inventories for each of the $m$ periods, and at most $C+1$ productions per state
  4. From $2^m$ setup plans
Explanation. States $O(mD)$ times attempts $O(C)$: pseudo-polynomial in the values $D$ and $C$.
dp-f-240 · level facile · notes
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?
  1. Every period produces its own demand
  2. 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$
  3. Every period produces exactly $4$
  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.
dp-f-288 · level teorema · notes
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?
  1. In $v(1,0)$
  2. In $v(m,0)$
  3. In $v(0,m)$
  4. 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)$.
dp-f-289 · level ipotesi · notes
Why does the Wagner–Whitin DP over the production runs not apply to capacitated lot sizing?
  1. With capacities zero-inventory ordering does not hold
  2. Because costs can be negative
  3. Because the network of runs has cycles
  4. Because demands are not integer
Explanation. With limited capacities a period may have to produce with units still in stock: a run no longer produces exactly $D_{j,t}$.
dp-f-290 · level teorema · notes
What is known about the complexity of single-item capacitated lot sizing?
  1. It is always polynomial
  2. It is NP-hard even without capacities
  3. With constant capacity it is NP-hard
  4. 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.
dp-f-291 · level ipotesi · notes
The DP for capacitated lot sizing takes $O(mDC)$ steps, with $D$ the total demand and $C$ the maximum capacity. Why is it pseudo-polynomial?
  1. Because the inventory is always zero
  2. Because the network has $2^m$ arcs
  3. The time depends on the values $D$ and $C$, not only on $m$
  4. Because $m$ is exponential
Explanation. The states are indexed by inventory quantities: the number of steps grows with the numerical values of the data.
dp-f-309 · level facile · notes
What does capacitated lot sizing (CLS) add to uncapacitated lot sizing?
  1. A limit $cap_t$ on the production of each period
  2. A limit on the final inventories
  3. More products
  4. Uncertain demands
Explanation. The constraint $x_t\le cap_t$ limits the production of each period.
dp-f-310 · level facile · notes
In the DP for capacitated lot sizing, what does the recurrence $v(t,k)$ choose in period $t$?
  1. The period of the last run
  2. Which product to make
  3. The capacity of the period
  4. The quantity $x$ produced in period $t$
Explanation. From the state $(t,k)$ with final inventory $k$ every production $x\le cap_t$ compatible with the demand $d_t$ is tried.

12. DP for the coin change problem (23)

dp-f-034 · level facile · notes
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$?
  1. $+\infty$
  2. $0$
  3. $2$
  4. $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.
dp-f-035 · level facile · notes
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?
  1. The CCP requires sum at most $c$ and minimizes the coins; the UKP requires weight exactly $c$ and maximizes the profit
  2. The CCP requires sum exactly $c$ and maximizes the coins; the UKP requires weight at most $c$ and minimizes the weight
  3. The CCP allows at most one coin per denomination; the UKP allows unlimited copies of every type
  4. 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.
dp-f-036 · level facile · notes
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?
  1. $\Theta(n^c)$
  2. $\Theta(c\log n)$, polynomial
  3. $\Theta(nc)$, pseudo-polynomial
  4. $\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.
dp-f-085 · level facile · notes
In coin change (CCP) the denominations $w_1,\dots,w_n$ are available in unlimited supply and the amount is $c$. What is a feasible solution?
  1. A binary vector $x$ with $\sum_j w_jx_j\ge c$
  2. An integer vector $x\ge 0$ with $\sum_j w_jx_j=c$
  3. An integer vector $x\ge 0$ with $\sum_j w_jx_j\le c$
  4. A subset of the denominations summing to $c$
Explanation. $x_j$ counts the coins of denomination $j$, and the sum must be exactly the amount. The objective minimizes $\sum_j x_j$.
dp-f-086 · level facile · notes
Coin change (CCP) with denominations $w=(4,6)$, in unlimited supply, and amount $c=9$. What is the minimum number of coins?
  1. No solution: even denominations cannot give an odd amount
  2. $2$
  3. $3$
  4. $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$.
dp-f-087 · level facile · notes
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?
  1. $12$
  2. $27$
  3. $64$
  4. $42$
Explanation. $(6+1)(2+1)(1+1)=7\cdot3\cdot2=42$; only those summing to exactly $6$ are feasible.
dp-f-088 · level facile · notes
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)$?
  1. $6$
  2. $1$
  3. $2$
  4. $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.
dp-f-089 · level facile · notes
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$?
  1. $k$: coins of $1$ are used
  2. $+\infty$: amount $k$ cannot be paid
  3. $0$: no coin is needed
  4. $-\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.
dp-f-090 · level facile · notes
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?
  1. Starting from $k=c$: take a coin $w_{s(k)}$ and set $k\leftarrow k-w_{s(k)}$, until $k=0$
  2. Take $v(c)$ coins of denomination $s(c)$
  3. Starting from $k=0$: take $w_{s(k)}$ and set $k\leftarrow k+w_{s(k)}$
  4. 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.
dp-f-091 · level facile · notes
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?
  1. Two: use or not use denomination $1$
  2. $k$, one per smaller amount
  3. Only one, with the largest denomination that fits
  4. 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.
dp-f-092 · level facile · notes
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)$?
  1. $2$
  2. $3$
  3. $4$
  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.
dp-f-093 · level facile · notes
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?
  1. None: with $p_j=1$ the two recurrences coincide
  2. Minimum instead of maximum, and $+\infty$ for unobtainable amounts because the sum must be exact
  3. Bounded copies instead of unlimited, and a two-dimensional table
  4. 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$.
dp-f-185 · level facile · notes
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?
  1. $\sum_jw_jx_j\ge c$
  2. $\sum_jw_jx_j=c$ with $x_j\in\Z_{\ge0}$
  3. $\sum_jw_jx_j\le c$ with $x_j\in\{0,1\}$
  4. $\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.
dp-f-186 · level facile · notes
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?
  1. $\Theta(nc)$, pseudo-polynomial: it depends on the value $c$, not on its length in bits
  2. $\Theta(n\log c)$, polynomial
  3. $\Theta(2^n)$, exponential in the number of denominations
  4. $\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.
dp-f-241 · level facile · notes
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?
  1. $(6,0,0)$ with $6$ coins; the greedy uses $3$
  2. $(0,2,0)$ with $2$ coins; the greedy uses $3$ ($4+1+1$)
  3. $(2,0,1)$ with $3$ coins; the greedy uses $3$
  4. $(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.
dp-f-242 · level facile · notes
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?
  1. $x_1\le6$, $x_2\le2$, $x_3\le1$
  2. $x_j\le1$ for every $j$
  3. $x_1\le6$, $x_2\le3$, $x_3\le2$
  4. $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$.
dp-f-243 · level facile · notes
The DP for coin change performs $S(n,c)=3+3c+3cn$ steps. How many are they with $n=3$ denominations and change $c=6$?
  1. $54$
  2. $21$
  3. $57$
  4. $75$
Explanation. $3+18+54=75$; the dominant term $3cn$ gives $\Theta(nc)$.
dp-f-292 · level teorema · notes
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?
  1. The minimum number of coins; $\Theta(c\log c)$
  2. The maximum value with $k$ coins; $\Theta(n^2)$
  3. The minimum number of coins for amount $k$; $\Theta(nc)$
  4. 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.
dp-f-293 · level ipotesi · notes
In the DP for coin change the amounts that cannot be formed have $v(k)=+\infty$ and not $0$. Why?
  1. Because $v(0)=+\infty$
  2. Change must be exact and the number of coins is minimized
  3. Because the denominations are positive
  4. Because the capacity may stay unused
Explanation. With $0$ an impossible amount would look best; $+\infty$ excludes it from the minimum. The instance is infeasible if $v(c)=+\infty$.
dp-f-294 · level teorema · notes
Denominations $\{1,3,4\}$, amount $6$. What do the greedy «largest coin that fits» and the DP for coin change give?
  1. Greedy $3$ coins ($4+1+1$), DP $2$ coins ($3+3$)
  2. Both $2$ coins
  3. Greedy $2$ coins, DP $3$ coins
  4. Both $3$ coins
Explanation. The greedy is not exact for arbitrary denominations; the DP always finds the minimum: $v(6)=2$.
dp-f-311 · level facile · notes
What does the coin change problem (CCP) ask?
  1. The maximum number of coins with value at most $c$
  2. The number of ways to form $c$
  3. The largest coin fitting into $c$
  4. The minimum number of coins forming exactly the amount $c$
Explanation. Each denomination is available in unlimited copies and the total must be exactly $c$.
dp-f-312 · level facile · notes
Denominations $\{1,2,5\}$, amount $11$. What is the minimum number of coins $v(11)$?
  1. $2$
  2. $5$
  3. $3$
  4. $4$
Explanation. $11=5+5+1$ with $3$ coins; with $2$ coins the maximum is $10$.
dp-f-313 · level facile · notes
Denominations $\{4,6\}$, amount $9$. What does the DP for coin change give?
  1. $v(9)=0$
  2. $v(9)=+\infty$: the instance is infeasible
  3. $v(9)=2$
  4. $v(9)=3$
Explanation. With even denominations only even amounts can be formed: $9$ cannot be formed.

13. DP for the rod cutting problem (28)

dp-f-037 · level facile · notes
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?
  1. $5$
  2. $16$
  3. $32$
  4. $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.
dp-f-038 · level facile · notes
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?
  1. The input contains the $n$ prices, hence $n$ grows with the instance size
  2. The prices $p_j$ are integer, hence the table has integer values
  3. The length $n$ is written in binary with $\log n$ digits
  4. 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.
dp-f-039 · level facile · notes
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?
  1. To forbid the rod without cuts, which is not a feasible pattern
  2. To guarantee that the rod is cut at least once
  3. To nothing: the recurrence never reads cell $v(0)$
  4. 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.
dp-f-094 · level facile · notes
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)$?
  1. $16$
  2. $5$
  3. $10$
  4. $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)$.
dp-f-095 · level facile · notes
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)$?
  1. $9$
  2. $11$
  3. $20$
  4. $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$.
dp-f-096 · level facile · notes
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?
  1. Starting from $\ell=1$ and adding pieces until the sum is $n$
  2. Read $v(n)$ and divide by the largest price
  3. Starting from $\ell=n$: cut a piece $s(\ell)$ and set $\ell\leftarrow\ell-s(\ell)$, until $\ell=0$
  4. 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.
dp-f-097 · level facile · notes
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$?
  1. Because the table starts at $\ell=1$
  2. With no piece length available a rod of positive length cannot be divided: no solution
  3. Because prices can be negative
  4. 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$.
dp-f-098 · level facile · notes
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?
  1. Cutting a piece of length $j$, with more pieces of the same length still allowed
  2. Not using pieces of length $j$
  3. Cutting a piece of length $j$ and moving to smaller lengths
  4. 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.
dp-f-099 · level facile · notes
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)$?
  1. $-\infty$
  2. $1$
  3. $10$
  4. $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$.
dp-f-100 · level facile · notes
For rod cutting with length $n$, the first DP uses a vector $v(\ell)$ and the second a table $v(j,\ell)$. How many steps do they take?
  1. The first $\Theta(n^2)$, the second $\Theta(n^3)$
  2. Both $\Theta(2^{n-1})$
  3. Both $\Theta(n^2)$
  4. The first $\Theta(n)$, the second $\Theta(n^2)$
Explanation. The first computes $n$ values, each with a maximum over at most $n$ terms; the second computes $(n+1)^2$ cells with two terms each.
dp-f-101 · level facile · notes
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?
  1. $32$
  2. $7$
  3. $16$
  4. $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.
dp-f-102 · level facile · notes
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?
  1. Type $j$ with weight $j$ and profit $p_j$, unlimited copies, total weight exactly $n$
  2. Type $j$ with weight $p_j$ and profit $j$, at most one copy, capacity $n$
  3. A single type of weight $1$ and profit $\max_j p_j$, capacity $n$
  4. 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.
dp-f-187 · level facile · notes
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?
  1. None: every scheme has a different vector
  2. Those with the same number of cuts
  3. Those with the same longest piece
  4. 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.
dp-f-188 · level facile · notes
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?
  1. $5$ schemes, maximum profit $10$
  2. $16$ schemes, maximum profit $13$
  3. $8$ schemes, maximum profit $10$
  4. $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$.
dp-f-189 · level teorema · notes
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?
  1. $\Theta(n^2)$, but pseudo-polynomial since it depends on $n$
  2. $\Theta(n^2)$; the input contains $n$ prices, so it is polynomial in the size
  3. $\Theta(2^n)$, like the enumeration of the schemes
  4. $\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.
dp-f-190 · level facile · notes
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?
  1. $\Theta(n^2)$, as the first: $n$ types times $n+1$ capacities
  2. $\Theta(n)$
  3. $\Theta(n^3)$
  4. $\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.
dp-f-244 · level facile · notes
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?
  1. $7$
  2. $120$
  3. $16$
  4. $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.
dp-f-245 · level facile · notes
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?
  1. $(0,1,0,0,1)$, profit $15$
  2. $(1,2,0,0,0)$, profit $11$
  3. $(2,1,0,0,0)$, profit $7$
  4. $(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$.
dp-f-246 · level facile · notes
The first DP for rod cutting computes $v(k)=\max_{1\le\ell\le k}\{p_\ell+v(k-\ell)\}$, with $v(0)=0$. With prices $p=(1,5,8,9)$, what is $v(4)$?
  1. $10$
  2. $9$
  3. $13$
  4. $8$
Explanation. $v(1)=1$, $v(2)=5$, $v(3)=8$, $v(4)=\max\{1+8,5+5,8+1,9+0\}=10$.
dp-f-247 · level facile · notes
In the first DP for rod cutting the computation of $v(k)$ tries $k$ lengths of the first piece. How many tries overall for a rod of length $n=4$?
  1. $16$
  2. $4$
  3. $8$
  4. $10$
Explanation. $1+2+3+4=n(n+1)/2=10$: hence $\Theta(n^2)$, compared to the $2^{n-1}$ schemes, which for large $n$ are far more.
dp-f-248 · level facile · notes
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?
  1. Because every length is used at most once
  2. Because the prices are integer
  3. Several pieces of the same length can be cut
  4. 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)$.
dp-f-249 · level facile · notes
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$?
  1. $8$
  2. $16$
  3. $10$
  4. $20$
Explanation. $4$ types times $4$ positive capacities: $16$ updates, $\Theta(n^2)$ as the first DP.
dp-f-295 · level teorema · notes
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?
  1. Because the profits are integer
  2. Because $n$ is written with $\log n$ bits
  3. Because the recurrence has one base case
  4. 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.
dp-f-296 · level ipotesi · notes
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$?
  1. Profits grow with the length
  2. The rod is cut into two pieces
  3. Each length can be cut any number of times
  4. Each length at most once
Explanation. The piece of length $j$ stays available: the residual rod is the same problem with length $\ell-j$.
dp-f-297 · level teorema · notes
In how many ways can a rod of integer length $n$ be cut into pieces of integer length, if the order of the pieces matters?
  1. $2^n$
  2. $2^{n-1}$
  3. $n!$
  4. $n^2$
Explanation. At each of the $n-1$ inner points one cuts or not: $2^{n-1}$ schemes, against $\Theta(n^2)$ steps of the DP.
dp-f-298 · level teorema · notes
After the DP for rod cutting the vector $s$ holds, for each length $\ell$, the first piece chosen. What is obtained, at no extra cost?
  1. An optimal solution for every length $\ell\le n$
  2. Only the solution for length $n$
  3. All optimal solutions
  4. A bound on the optimal value
Explanation. For each $\ell$ one follows $s[\ell], s[\ell-s[\ell]],\dots$ down to $0$.
dp-f-314 · level facile · notes
Rod of length $4$, profits $p_1=1$, $p_2=5$, $p_3=8$, $p_4=9$. What is the maximum profit $v(4)$?
  1. $10$
  2. $9$
  3. $8$
  4. $11$
Explanation. Two pieces of length $2$ give $5+5=10$; $3+1$ gives $9$ and the whole rod $9$.
dp-f-315 · level facile · notes
In the DP for rod cutting, why is $v(0)=0$?
  1. Because $p_0=0$ is given
  2. Because the rod must be cut at least once
  3. Because the maximum profit is $0$
  4. A rod of length $0$ gives no pieces and no profit
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)$?
  1. $13$
  2. $4$
  3. $9$
  4. $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)$?
  1. $25$
  2. $14$
  3. $34$
  4. $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$?
  1. $v(4,11)=27$, $\tilde S=\{2,3\}$
  2. $v(4,11)=25$, $\tilde S=\{2,4\}$
  3. $v(4,11)=34$, $\tilde S=\{1,3,4\}$
  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$?
  1. $v(4,11)=38$, $\tilde S=\{1,3,4\}$
  2. $v(4,11)=29$, $\tilde S=\{2,3,4\}$
  3. $v(4,11)=31$, $\tilde S=\{1,2,3\}$
  4. $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$.

3. DP for the unbounded knapsack problem (2)

Example 1 · dp-g-ukp-dp · level facile · notes
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)$?
  1. $36$
  2. $40$
  3. $39$
  4. $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.
Example 2 · dp-g-ukp-dp · level facile · notes
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)$?
  1. $29$
  2. $31$
  3. $34$
  4. $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.
Example 1 · dp-g-ukp-sol · level media · notes
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?
  1. $22$ with $x=(2,0,0)$
  2. $24$ with $x=(1,0,1)$
  3. $26$ with $x=(0,0,2)$
  4. $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$.
Example 2 · dp-g-ukp-sol · level media · notes
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?
  1. $36$ with $x=(0,0,3)$
  2. $33$ with $x=(3,0,0)$
  3. $29$ with $x=(1,1,1)$
  4. $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$.

4. DP for the bounded knapsack problem (2)

Example 1 · dp-g-bkp-dp · level facile · notes
Bounded knapsack (BKP): type $j$ has profit $p_j$, weight $w_j$ and $b_j$ available copies, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 4 & 3 & 4\\ w_j & 5 & 2 & 4\\ b_j & 1 & 1 & 2\end{array}$, capacity $c=10$. 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 the optimal value $v(3,10)$?
  1. $12$
  2. $8$
  3. $11$
  4. $15$
Explanation. The DP gives $v(3,10)=11$. With one copy per type (KP) one would get $8$, with unlimited copies (UKP) $15$.
Example 2 · dp-g-bkp-dp · level facile · notes
Bounded knapsack (BKP): type $j$ has profit $p_j$, weight $w_j$ and $b_j$ available 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=11$. 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 the optimal value $v(3,11)$?
  1. $29$
  2. $26$
  3. $30$
  4. $39$
Explanation. The DP gives $v(3,11)=29$. With one copy per type (KP) one would get $26$, with unlimited copies (UKP) $39$.
Example 1 · dp-g-bkp-cella · level media · notes
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)$?
  1. $11$
  2. $5$
  3. $12$
  4. $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$.
Example 2 · dp-g-bkp-cella · level media · notes
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)$?
  1. $11$
  2. $29$
  3. $34$
  4. $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$.

5. DP for the subset sum problem (2)

Example 1 · dp-g-ssp-dp · level facile · notes
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}$?
  1. $27$
  2. $26$
  3. $21$
  4. $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.
Example 2 · dp-g-ssp-dp · level facile · notes
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}$?
  1. $20$
  2. $22$
  3. $26$
  4. $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.
Example 1 · dp-g-ssp-count · level media · notes
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?
  1. $3$
  2. $5$
  3. $2$
  4. $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$.
Example 2 · dp-g-ssp-count · level media · notes
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?
  1. $12$
  2. $11$
  3. $14$
  4. $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)

Example 1 · dp-g-mckp-dp · level facile · notes
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)$?
  1. $8$
  2. $7$
  3. $9$
  4. $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$).
Example 2 · dp-g-mckp-dp · level facile · notes
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)$?
  1. $17$
  2. $16$
  3. $22$
  4. $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$).
Example 1 · dp-g-mckp-sol · level media · notes
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 & 6 & 8 & 2 & 6 & 9 & 9\\ w_j & 4 & 6 & 5 & 4 & 1 & 2\end{array}$, capacity $c=11$; exactly one item per class is chosen. Which choice of items is optimal (the optimal solution is unique), and what is its value?
  1. $\{1,4,5\}$, value $21$
  2. $\{1,4,6\}$, value $21$
  3. $\{1,3,5\}$, value $17$
  4. $\{2,4,5\}$, value $23$
Explanation. The DP by classes and the backward reconstruction give $\{2,4,5\}$, of value $23$; the second best feasible choice is worth $21$.
Example 2 · dp-g-mckp-sol · level media · notes
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 & 5 & 4 & 5 & 8 & 9 & 7\\ w_j & 6 & 1 & 6 & 4 & 5 & 6\end{array}$, capacity $c=15$; exactly one item per class is chosen. Which choice of items is optimal (the optimal solution is unique), and what is its value?
  1. $\{2,3,5\}$, value $18$
  2. $\{2,4,5\}$, value $21$
  3. $\{2,4,6\}$, value $19$
  4. $\{1,4,5\}$, value $22$
Explanation. The DP by classes and the backward reconstruction give $\{1,4,5\}$, of value $22$; the second best feasible choice is worth $21$.

7. DP for the multidimensional knapsack problem (2)

Example 1 · dp-g-mdkp-dp · level facile · notes
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?
  1. $12$
  2. $13$
  3. $20$
  4. $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.
Example 2 · dp-g-mdkp-dp · level facile · notes
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?
  1. $16$
  2. $23$
  3. $18$
  4. $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.
Example 1 · dp-g-mdkp-sol · level media · notes
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. $\{1\}$
  2. $\{2\}$
  3. $\{1,2\}$
  4. $\{2,4\}$
Explanation. $\{2,4\}$ respects both capacities and is worth $12$; the second best feasible solution is worth $9$.
Example 2 · dp-g-mdkp-sol · level media · notes
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. $\{1,2,3\}$
  2. $\{2,3,4\}$
  3. $\{1,2\}$
  4. $\{1,3,4\}$
Explanation. $\{1,2,3\}$ respects both capacities and is worth $25$; the second best feasible solution is worth $22$.

8. DP for the knapsack problem with setups (2)

Example 1 · dp-g-kps-dp · level facile · notes
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?
  1. $8$
  2. $10$
  3. $7$
  4. $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$.
Example 2 · dp-g-kps-dp · level facile · notes
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?
  1. $5$
  2. $13$
  3. $10$
  4. $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$.
Example 1 · dp-g-kps-sol · level media · notes
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?
  1. $\{2\}$
  2. $\{1\}$
  3. $\{3\}$
  4. $\{4\}$
Explanation. $\{4\}$ is worth $6$, setups included; the second best solution is worth $4$.
Example 2 · dp-g-kps-sol · level media · notes
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?
  1. $\{2,3\}$
  2. $\{2,4\}$
  3. $\{4\}$
  4. $\{1,2\}$
Explanation. $\{1,2\}$ is worth $6$, setups included; the second best solution is worth $5$.

9. DP for the multiple knapsack problem (2)

Example 1 · dp-g-mkp-dp · level facile · notes
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?
  1. $22$
  2. $17$
  3. $16$
  4. $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.
Example 2 · dp-g-mkp-dp · level facile · notes
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?
  1. $20$
  2. $21$
  3. $19$
  4. $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.
Example 1 · dp-g-mkp-sol · level media · notes
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. $\{1,2,3\}$
  2. $\{1,2,4\}$
  3. $\{1,2,3,4\}$
  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$.
Example 2 · dp-g-mkp-sol · level media · notes
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. $\{1,2,3\}$
  2. $\{1,4\}$
  3. $\{1,3\}$
  4. $\{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)

Example 1 · dp-g-uls-cjt · level facile · notes
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)?
  1. $225$
  2. $135$
  3. $275$
  4. $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.
Example 2 · dp-g-uls-cjt · level facile · notes
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)?
  1. $610$
  2. $325$
  3. $365$
  4. $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.
Example 1 · dp-g-uls-ww · level media · notes
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)$?
  1. $180$
  2. $190$
  3. $280$
  4. $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$.
Example 2 · dp-g-uls-ww · level media · notes
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)$?
  1. $265$
  2. $400$
  3. $310$
  4. $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?
  1. $v(5)=310$, runs in periods $1,2,3,4,5$
  2. $v(5)=220$, runs in periods $1,2,5$
  3. $v(5)=375$, runs in periods $1$
  4. $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?
  1. $v(5)=210$, runs in periods $1,4,5$
  2. $v(5)=200$, runs in periods $1,3,5$
  3. $v(5)=280$, runs in periods $1,2,3,4,5$
  4. $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}$.

11. DP for the capacitated lot sizing problem (2)

Example 1 · dp-g-cls-dp · level facile · 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 & 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)$?
  1. $31$
  2. $38$
  3. $29$
  4. $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$.
Example 2 · dp-g-cls-dp · level facile · 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}$. With the DP on the states $(t,k)$ (period, final stock), what is the optimal cost $v(3,0)$?
  1. $23$
  2. $33$
  3. $22$
  4. $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?
  1. $x=(3,3,3)$, cost $42$
  2. $x=(5,4,0)$, cost $40$
  3. $x=(3,6,0)$, cost $34$
  4. $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?
  1. $x=(5,0,4)$, cost $25$
  2. $x=(2,2,5)$, cost $33$
  3. $x=(4,0,5)$, cost $22$
  4. $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.

12. DP for the coin change problem (2)

Example 1 · dp-g-ccp-dp · level facile · notes
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)$?
  1. $6$
  2. $10$
  3. $5$
  4. $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.
Example 2 · dp-g-ccp-dp · level facile · notes
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)$?
  1. $6$
  2. $4$
  3. $5$
  4. $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$?
  1. $10$
  2. $12$
  3. $9$
  4. $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$?
  1. $5$
  2. $7$
  3. $9$
  4. $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.

13. DP for the rod cutting problem (2)

Example 1 · dp-g-rcp-dp · level facile · notes
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)$?
  1. $22$
  2. $15$
  3. $25$
  4. $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.
Example 2 · dp-g-rcp-dp · level facile · notes
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)$?
  1. $10$
  2. $18$
  3. $15$
  4. $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.
Example 1 · dp-g-rcp-sol · level media · notes
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)?
  1. $22$: pieces $6$
  2. $24$: pieces $3+3$
  3. $18$: pieces $1+1+1+1+1+1$
  4. $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$.
Example 2 · dp-g-rcp-sol · level media · notes
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)?
  1. $25$: pieces $1+1+1+1+1$
  2. $22$: pieces $2+1+1+1$
  3. $15$: pieces $5$
  4. $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$.