File HouseProblems.h

↰ Parent directory (ADS/optimization)

Two problems of dynamic programming on a row of n houses, where the choice of each house depends only on the one of its neighbour:

Definition (ADS/optimization/HouseProblems.h)

Detailed Description

  • the largest sum of the items of A, no two of them adjacent (the donations of houses no two of which are neighbours, the maximum weight independent set of a path): :math:` D[ i ] = max( D[ i - 1 ] , D[ i - 2 ] + A_{i-1} ) , D[ 0 ] = D[ -1 ] = 0; maxNonAdjacentSum() in :math: Theta( n ) ` time and O( 1 ) space, nonAdjacentSelection() with the places read back from the table, :math:` Theta( n ) ` space. It is the weighted intervals of section 13.2 [see File WeightedIntervals.h] with the unit intervals [ i , i + 2 ).

  • paintHouses(): the cheapest painting of the houses with k colors, cost[ h ][ c ] for the house h of color c, two adjacent houses of different colors: :math:` D[ h ][ c ] = cost[ h ][ c ] + min_{p neq c} D[ h - 1 ][ p ] , which is O( n k^2 ) as written; keeping of each row its least value, its color and its second least value, the least over :math: p neq c ` is one of the two, and the time is O( n k ), the colors read back from the table of O( n k ) space.

Both are shortest paths in the DAG of the states (house, choice), and generalize to a tree of houses by the same recurrence on the children.

The contracts [see File Contract.h]: the rows of cost have the same number k of colors, k >= 2 for two houses or more; the places chosen are increasing and not adjacent, the colors of adjacent houses differ, and both give the value found. The functions are defined in HouseProblems.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 13.2, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

  1. Kleinberg, E. Tardos, Algorithm Design, Addison-Wesley, 2005, section 6.1

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions