假设你要去伦敦度假,假期两天,但你想去游览的地方很多。你没法前往每个地方游览,因此你列个单子。
对于想去游览的每个名胜,都列出所需的时间以及你有多想去看看。根据这个清单,你能确定该去游览哪些名胜吗?
这也是一个背包问题!但约束条件不是背包的容量,而是有限的时间;不是决定该装入哪些商品,而是决定该去游览哪些名胜。请根据这个清单绘制动态规划网格,再接着往下读。
网格类似于下面这样。
你画对了吗?请填充这个网格,决定该游览哪些名胜。答案如下。