随便说说

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

试一试

贪心法解决背包问题 重量:
价值:
重量:
贪心法求最优价值:

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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);
}