Algorithms and Data Structures for Programming Contests
Dynamic Programming (Cont'd)
Regroup (2)
High-level solution?
- Is it recursive?
- Yes: solution either does not use last song or it does
(in which case capacity is reduced accordingly).
- Does it have optimal substructure?
- Yes:
if optimal solution does not use last song,
then it is optimal (highest total rating) for rest of songs
and original capacity;
if optimal solution uses last song,
then it is optimal for rest of songs
and reduced capacity.
- Are subproblems "simple"?
- Yes:
each subproblem characterized by
capacity (range [0..C]) and
index of last song considered (range [0..N]).
- Do subproblems overlap?
- Yes:
small subproblems (e.g., with N = 1)
must be evaluated multiple times as part of
solving larger problems.
Step 1: define a table of solutions.
- For indices
c ∈ [0..C] and
n ∈ [0..N],
let table[c,n] =
maximum total rating of songs selected from 1,...,n
that fit within capacity c.
Step 2: write recursive equations for table values.
- Base cases:
- table[0,n] = 0
for n = 0,...,N — no song can fit within capacity 0;
- table[c,0] = 0
for c = 0,...,C — no song to pick.
- General case:
for c = 1,...,C
and n = 1,...,N:
- let sn = size(song n)
and rn = rating(song n);
- if sn > c,
table[c,n] =
table[c,n−1] — song n cannot be used;
- else,
table[c,n] =
max(table[c,n−1],
table[c−sn,n−1] + rn) — either don't use song n,
or use it and do best possible with remaining capacity.
Step 3: write the algorithm.
- Simple nested loops (outer loop on n)
to compute table values according to the recurrence.
Step 4: reconstruct the solution.
- Not necessary for problem,
but would be done just like for previous problem.
Further examples
- Matrix chain multiplication.
- Making change.
To learn more...
© Copyright 2012–2015 François Pitt
<francois.pitt@utoronto.ca>
last updated at 08:24 (EST) on Thu 5 Mar 2015
Algorithms and Data Structures by
François Pitt is licensed under a
Creative
Commons Attribution-ShareAlike 4.0 International License.