問答題

【簡答題】什么是偽多項(xiàng)式時(shí)間的算法？如何用動(dòng)態(tài)規(guī)劃法求解背包問題？

答案：定義：設(shè)實(shí)例I的輸入規(guī)模為n，實(shí)例中的最大數(shù)為max（I），若算法的時(shí)間復(fù)雜性以某個(gè)二元多項(xiàng)式p（n，max（I））為上...

你可能感興趣的試題

【簡答題】什么是多項(xiàng)式時(shí)間近似方案（PTAS）？什么是完全多項(xiàng)式時(shí)間近似方案（FPTAS，F(xiàn)PAS）？

答案：多項(xiàng)式時(shí)間近似方案（PTAS，Polynomial Time Approximation ...

【簡答題】什么是算法A對于實(shí)例I的近似比、A的絕對近似比和漸進(jìn)近似比？

答案：算法A對于實(shí)例I的近似比（ratio factor）=RA（I）=max{A（I）/OPT（I），OPT（I）...