js贪心算法---背包问题

/** @param {Object} capacity 背包容量 6* @param {Object} weights 物品重量 [2,3,4]* @param {Object} values 物品价值 [3,4,5]*///贪心算法，只能算，可以分割的物品，如果不能分割物品，只能得到近似解，不分割物品，可以使用动态规划//1、计算每件商品的（价格/质量），即单位质量的价值//2、将单位质量价值排序//3、逐个取出console.log(tanx(6,[2,3,4],[3,4,5]));function tanx(capacity,weights,values){var list = [];for(var i = 0,len = weights.length; i < len; i++){list.push({num:i+1, //第几件商品w:weights[i], //重量v:values[i],rate:values[i]/weights[i] });}list.sort(function(a,b){if(a.rate > b.rate){return -1;}else{return 1;}});var selects = [];var total = 0;for(var i = 0,len = list.length; i < len; i++){var item = list[i];if(item['w'] <= capacity){selects.push({num:item.num,rate:1 , //完整的商品记录为1v:item.v,w:item.w});total = total + item.v;capacity = capacity - item.w;}else if(capacity > 0){//选取不完整的商品var rate = capacity/item['w'];var v = item.v*rate;selects.push({num:item.num,rate: rate,v:item.v*rate,w:item.w*rate});total = total + v;break;}else{break;}}return {selects,total}}

　　

转载于:https://www.cnblogs.com/muamaker/p/9391333.html

总结

以上是生活随笔为你收集整理的js贪心算法---背包问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。