Miscellaneous problems

Catalogue of combinatorial problems · Catalogue (PDF)

• In the rod cutting problem a rod of length \(n\) is cut into pieces of integer length \(\ell\) with profits \(p_\ell\); the total length of the pieces equals \(n\) and their total profit is maximized.

• In the coin change problem an amount \(c\) is returned with coins of the denominations \(w_1,\dots,w_n\), each in unlimited supply; the total value equals \(c\) and the number of coins is minimized.

Problem	Acronym	Difference
Rod cutting problem	RCP	An unbounded knapsack with one item type per piece length \(\ell\), weight \(\ell\), profit \(p_\ell\) and capacity \(n\), where the total length must be exactly \(n\).
Coin change problem	CCP	Like the UKP it has unlimited copies of every item type, but it asks for exactly \(c\) and minimizes the number of coins, while the UKP asks for at most \(c\) and maximizes the profit.