chapter_greedy/fractional_knapsack_problem/

[giscus[bot]]

chapter_greedy/fractional_knapsack_problem/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_greedy/fractional_knapsack_problem/

[jiaowobaba02]

讲的很清楚，一遍就看懂了

[CQNKSJTU]

Sort 不算时间复杂度吗

[krahets]

谢谢指正！排序使用 $O(n \log n)$ 的时间

[qqqq11116666]

HELLO world

[Harbour-z]

清晰易懂，感谢k神！

[csj-9-9]

感谢K神的付出，文章内容质量确实非常好！但请原谅我的强迫症：“容量”给人的第一印象应该不是指“重量”，而是是指“体积”

[ztkuaikuai]

通俗易懂(๑•̀ㅂ•́)و✧

[RocGit]

C# 的计算结果有出入，如果v, w是int类型， item.v / item.w 从高到低进行排序和预想的不一样，最后结果也不一样
Array.Sort(items, (x, y) => (y.v / y.w).CompareTo(x.v / x.w));
改成：Array.Sort(items, (x, y) => (y.v * 1.0d / y.w).CompareTo(x.v * 1.0d / x.w)); 会好一些

[xgeeek]

kotlin 的排序写错了吧 应该是 sortByDescending

[syutengu]

图15-6数形结合秒变小学算术题。

[sinabs]

类似的leetCode算法题
https://leetcode.cn/problems/maximum-bags-with-full-capacity-of-rocks/

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        // 创建物品列表，包含两个属性：总量、已使用量
        Item[] items = new Item[capacity.length];
        for (int i = 0; i < capacity.length; i++) {
            items[i] = new Item(capacity[i], rocks[i]);
        }

        // 剩余量最少的背包排在最前面, 这样用最少石头舔更多背包
        Arrays.sort(items, Comparator.comparingInt(item -> item.total - item.used));

        int res = 0;
        for (Item item : items) {
            //获得背包剩余量
            int left = item.total - item.used;
            //已经满了的背包就不用添加了
            if (left == 0) {
                res++;
            //放置的额外石头的left个数, 使其背包填满
            }else if(left <= additionalRocks) {
                additionalRocks -= left;
                res++;
            }
        }
        return res;
    }

}

class Item {
    int total;  //总量
    int used;   //已使用量
    public Item(int total, int used){
        this.total = total;
        this.used = used;
    }
}