/** @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}}
)
