<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>贪心算法</title>
</head>
<body>
    <script>
        var need = 0.63 * 100;
        function makeChange (need) {
            var coins = []

            var _25 = 0.25 * 100
            coins[0] = parseInt(need / _25)
            if (coins[0]) need = need % _25
            
            var _1 = 0.1 * 100
            coins[1] = parseInt(need / _1)
            if (coins[1]) need = need % _1

            var _01 = 0.01 * 100
            coins[2] = parseInt(need / _01)
            return coins
        }
        console.group('找美元的问题')
        console.log(makeChange(need))
        console.groupEnd()

        function greedy (values, weights, capacity, n) {
            var weight = 0; // 容量
            var i = 0;
            var value = 0; // 价值

            while(weight < capacity && i < n) {
                if (weights[i] <= capacity-weight) { // 如果放得下则选择最有价值的
                    value += values[i] // 总价值增加
                    weight += weights[i] // 总尺寸增加
                } else {
                    value += (capacity-weight)/weights[i] * values[i] // 处理容量不够的情况
                    weight = capacity // 直接将容量装满
                }
                i++
            }

            return value
        }
        var values = [50, 140, 60, 60];
        var weights = [5, 20, 10, 12];
        var capacity = 30;

        console.group('背包问题 --- 贪心算法')
        console.log(greedy(values, weights, capacity, weights.length))
    </script>
</body>
</html>

External CSS

This Pen doesn't use any external CSS resources.

External JavaScript

This Pen doesn't use any external JavaScript resources.