虑分数背包问题,定义如下:给出n 个大小为 s1, s2, …, sn , 价值为v1, v2, …, vn 的物品, 并设背包容量为C, 要找到非负实数x1, x2, …, xn, 使和 在约束 下最大。写出求解问题的贪心算法,估计算法的时间复杂性。
参考答案:float knapsack(float c, float s[], float v[], float x[]) { int n=v.length; Element [] d = new Element [n]; for (int i = 0; i < n; i++) d[i] = new Element(s[i], v[i...
查看答案