随便说说

如果需要了解贪心法，请看这篇硬币问题
贪心法相较来说更加简洁，这里就不展开了。

试一试

贪心法解决背包问题

重量：
价值：
重量：
贪心法求最优价值：

代码

function greedy(values, weights, capacity)
    {
    var returnValue = 0
    var remainCapacity = capacity
    var sortArray = []
    values.map((cur, index) =>
    {
        sortArray.push(
        {
        'value': values[index],
        'weight': weights[index],
        'ratio': values[index]/weights[index]
        })
    })
    sortArray.sort(function(a, b){
        return b.ratio - a.ratio
    })
    console.log(sortArray)
    sortArray.map((cur,index) =>
    {
        var num = parseInt(remainCapacity/cur.weight)
        console.log(num)
        remainCapacity -= num*cur.weight
        returnValue += num*cur.value
    })
    return returnValue
    }
    document.getElementById('submit').onclick = function(event)
    {
        var capacity =parseInt(document.getElementById('c').value);
        var  v_str =  document.getElementById('v').value ;
        var  values = v_str.split( ',' );
        var  w_str =  document.getElementById('w').value ;
        var  weights = w_str.split( ',' );

        console.log(greedy(values, weights, capacity)) // 320
        document.getElementById("bv").innerHTML = greedy(values, weights, capacity);
    }