1.請找出一個不適用最佳化問題原則的例子(即表示無法使用 dynamic programming解題)。請證明你的答案。
- bean_bottom_2Lv 51 0 年前最佳解答
Dynamic programming is used for problems that can be divided into small pieces, each one overlaps the other and each one of them will require the result from another one. Good example is Fibonacci numbers when F(n) needs F(n-1) and F(n-2).
So, if a problem can be divided into smaller pieces but each pieces are independent to each other. Thus, none of the results can be used by another. This will not be a good candidate for dynamic programming.
Given an integer X, find the largest prime P and P < X.
You can divide this up to smaller pieces (partitioning X) but none of the pieces will give you optimal structure and none of them will give any results that can be use to evolve to a best solution.