且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

我们可以解决“整齐打印”吗?使用贪婪算法而不是动态编程的问题?

更新时间:2022-03-23 23:13:09

否,因为贪婪算法通常是短视的现在的决定(决定当前行的单词数)最终迫使更高的成本。例如,假设我们每行可以有10个字符。

No, because as is often the case with greedy algorithms, short sighted decisions now (deciding how many words for the current line) end up forcing higher cost later. For example, suppose we can have 10 chars per line.

贪心解决方案

xx xxx xx    cost = 1
xxxxx        cost = 125
xxxxx        cost = 0 (last line)

更好的解决方案

xx xxx       cost = 64
xx xxxxx     cost = 8
xxxxx        cost = 0 (last line)

贪婪的解决方案在第一行添加了更多单词,但这实际上会产生更高的总解决方案成本。

The greedy solution packs more words onto the first line, but that actually produces a higher total solution cost.