首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
具体算法可描述如下：
void Knapsack（int n，float M，float v[]，float w[]，float x[]）
{Sort（n，v，w）；
int i；
for（i=1；i<=n；i++） x[i]=0；
float c=M；
for（i=1；i<=n；i++）
{if（w[i]>c） break；
x[i]=1；
c-=w[i]；
}
if（i<=n）x[i]=c/w[i]；
}
（简答题）
用贪心算法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。
正确答案
答案解析
略
相似试题
（填空题）
0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。
（简答题）
举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
（填空题）
用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。
（填空题）
许多可以用贪心算法求解的问题一般具有2个重要的性质：（）性质和（）性质。
（简答题）
使用回溯法解0/1背包问题：n=3，C=9，V={6，10，3}，W={3，4，4}，其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
（简答题）
描述0-1背包问题。
（单选题）
能采用贪心算法求最优解的问题，一般具有的重要性质为：（）
（填空题）
贪心算法总是做出在当前看来（）的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的（）。
（简答题）
有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为多少？
