上文说到，贪心算法基于当前的现状，找到最优的选择进行决策。
这个问题其实就是个性价比的问题，性能就是价值val，价格就是重量wgt，这里不能称为价格了，应该叫代价。
那么，如果我们每次选择的时候，都尽可能使用性价比最高的那个物品，是不是就可以找到最佳的选择了？
这里的性价比，就是 val / wgt
当然，因为可以选择方案中的物品的一部分，实际价值 = 单位价值 * wgt
我们把每个物品的性价比计算一下，排个序，是不是就能看出来哪个物品性价比最高？那么剩下的策略就是每次优先选择性价比最高的那个。
/* 物品 */
class Item {
int w; // 物品重量
int v; // 物品价值
public Item(int w, int v) {
this.w = w;
this.v = v;
}
}
/* 分数背包：贪心 */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
// 创建物品列表，包含两个属性：重量、价值
Item[] items = new Item[wgt.length];
for (int i = 0; i < wgt.length; i++) {
items[i] = new Item(wgt[i], val[i]);
}
// 按照单位价值 item.v / item.w 从高到低进行排序
Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
// 循环贪心选择
double res = 0;
for (Item item : items) {
if (item.w <= cap) {
// 若剩余容量充足，则将当前物品整个装进背包
res += item.v;
cap -= item.w;
} else {
// 若剩余容量不足，则将当前物品的一部分装进背包
res += (double) item.v / item.w * cap;
// 已无剩余容量，因此跳出循环
break;
}
}
return res;
}