- 搜標題
- 搜題干
- 搜選項
問答題
【計算題】分別用貪心算法、動態(tài)規(guī)劃法、回溯法設(shè)計0-1背包問題。要求：說明所使用的算法策略；寫出算法實現(xiàn)的主要步驟；分析算法的時間。
答案：
（1）貪心算法O（nlog（n））
首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多...
首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多...
你可能感興趣的試題
問答題
【計算題】
假設(shè)有7個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹。
答案：
貪心算法：
（1）標準：重量、價值和單位價值。
（2）使用重量從小到大：FGBAEDC。得到貪心解為...
（1）標準：重量、價值和單位價值。
（2）使用重量從小到大：FGBAEDC。得到貪心解為...
