今天做了一家公司的笔试题，里面一道编程题就是贪心算法来解决的，就是类似经典的背包问题。之前只是看过，笔试的时候凭借印象居然做出来80%，心情非常愉悦，记录一下。
原来的题目我不记得了，写个类似的题目。
背包问题是一个组合优化的问题，描述如下：给一个固定大小，能够携重W的背包以及一组有价值重量的物品，找出一个最佳的方案，使得装入包中的物品重量不超过W且总价值最大。
1、问题分析
数据：物品个数n=5,物品重量weights=[2，2，6，5，4],物品价值values=[6，3，5，4，6],背包总容量W=10。
2、问题思路
* 先计算出每一个物品的性价比，就是重量/价值，得到每个物品的性价比，存进去一个数组，按照从小到大排列。之后遍历这个数组，在容量>=0之前，增加max的值。
* 代码如下：
let price = [2,2,3,1,5,2]; // 价格
let nums = [2,3,1,5,4,3]; // 对应的数量
let money = 6; // 有多少钱
tanxin(price,nums,money)
function tanxin(price,nums,money){
// 要返回的值
let max = 0;
// 现在剩下多少钱
let endMoney = money;
let arr = [];
// 遍历价格，把价格，数量，和比例存进一个数组
price.forEach((ele,idx)=>{
arr.push({
‘price‘:price[idx],
‘num‘:nums[idx],
‘bili‘:price[idx]/nums[idx]
})
})
// 做一下排序，从小到大排
arr.sort((a,b)=>{
return a.bili - b.bili
})
// 遍历物品数组
arr.forEach((ele,idx)=>{
// 需要限定当大于0时，不然会一直加下去
if(endMoney - ele.price>=0){
// 剩下的钱减少
endMoney = endMoney - ele.price;
// 可以买的物品最大数量增加
max += ele.num
}
})
console.log(max)
}
原文：https://www.cnblogs.com/linxf/p/12589624.html