上文说到，贪心算法基于当前的现状，找到最优的选择进行决策。
这个问题其实就是个性价比的问题，性能就是价值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;
}