分数背包问题

问题描述：给定 n 个物品，第 i 个物品的重量为 wgt[i−1]、价值为 val[i−1] ，和一个容量为 cap 的背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问在限定背包容量下背包中物品的最大价值

贪心算法

• 计算每件物品的单位重量价值：val[i-1]/wgt[i-1] 按照每件物品的单位重量价值进行排序
• 遍历所有物品，每轮贪心地选择单位价值最高的物品。
• 若剩余背包容量不足，则使用当前物品的一部分填满背包。

const wgt=[2,5,3,7,5]
const val=[3,10,4,2,20]
const cap= 14
class Item{
    constructor(w,v){
        this.w=w;
        this.v=v;
    }
   }
function scoreBackpack(val,wgt,cap){
    const items=val.map((v,i)=>
        new Item(wgt[i],v)
    )
    //按照单位重量价值来从高到低进行排序
    items.sort((a,b)=>b.v/b.w-a.v/a.w)
    let res=0;
    //遍历每个物品，按照排序号的items来放进背包
    for (const item of items) {
        //如果当前item能放进背包
        if(item.w<cap){
            res +=item.v;
            cap -=item.w;
        }else{
            //不能，就将部分item放进背包
            res+= (item.v/item.w) * cap
            //无剩余容量就跳出循环
            break
        }
    }
    return res
}

reference