考慮下述背包問(wèn)題的實(shí)例。有5件物品，背包容量為100？貪心算法在求解問(wèn)題時(shí)總是做出最佳選擇（但結(jié)果可能不是最好的）典型算法：prim算法和Kruskal算法分治算法的基本思想是將一個(gè)N尺度的問(wèn)題分解成

考慮下述背包問(wèn)題的實(shí)例。有5件物品，背包容量為100？

貪心算法在求解問(wèn)題時(shí)總是做出最佳選擇（但結(jié)果可能不是最好的）

典型算法：prim算法和Kruskal算法

分治算法的基本思想是將一個(gè)N尺度的問(wèn)題分解成k個(gè)較小的子問(wèn)題，

這些子問(wèn)題相互獨(dú)立，性質(zhì)與原問(wèn)題的原問(wèn)題解相同。

典型算法：河內(nèi)塔，對(duì)分搜索

動(dòng)態(tài)規(guī)劃，通過(guò)將原問(wèn)題分解成相對(duì)簡(jiǎn)單的子問(wèn)題來(lái)解決復(fù)雜問(wèn)題的一種方法

典型算法：背包問(wèn)題

回溯算法，也稱為試算法，是一種系統(tǒng)地搜索問(wèn)題解的方法

典型算法：八皇后問(wèn)題

根據(jù)單位權(quán)值的最大優(yōu)先級(jí)策略目前看來(lái)是最好的（結(jié)果不一定是最好的）

這里是貪心算法，考慮到0/1背包問(wèn)題，1，2，3的最大值是430（50，200，180）

考慮到部分包含，1，2，3，4（4，40）的最大值是630（50，200，180）]225/45*40）

2，3，4的最大值確實(shí)是605，但不是用貪心算法計(jì)算出來(lái)的

所以答案是C

0-1背包問(wèn)題不能用貪心方法求解，但有些背包問(wèn)題可以用貪心方法求解。

首先，如果您不帶0-1背包，您必須帶上所有這些物品。網(wǎng)頁(yè)鏈接可參考此查看