贪心算法:
算法GREEDY_KANPSACK
输入：表示背包容量的实数C,物品数n,表示n个物品的体积和价值的实数数组s[1..n]和v[1..n]。
输出：装入背包物品的最大总价值maxv和相应的最优解x[1..n]。
for i=1 to n
y[i]=v[i]/s[i]//求n个物品的单位体积价值y[1..n]。
end for
//对y[1..n]按降序地址排序，排序结果返回到数组d[1..n]//中,使得
y[d[1]]>=y[d[2]]>=…>=y[d[n]]。
d=sort(y, n)
for i=1 to nx[i]=0//对x[1..n]初始化。
i=1;maxv=0;rc=C//以下rc表示当前背包的剩余容量。
while rc>0 and i<=n
j=d[i]// u
j为当前考虑选择的物品
if s[j]<=rc then
x[j]=1;rc=rc-s[j]//物品u
j全部装入背包。else
x[j]=rc/s[j]//选择物品u
j的一部分将背包填满。
rc=0
end if
maxv=maxv+v[j]*x[j]
i=i+1
end while
return maxv, x[1..n]
end GREEDY_KNAPSACK
●算法的时间复杂性：Θ(nlogn)
间)
思考：0/1背包问题可否用贪心法解？(主要为排序的时
