算法学习笔记（7.1）-贪心算法（分数背包问题）

##问题描述

给定 𝑛 个物品，第 𝑖 个物品的重量为 𝑤𝑔𝑡[𝑖−1]、价值为 𝑣𝑎𝑙[𝑖−1] ，和一个容量为 𝑐𝑎𝑝 的背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问在限定背包容量下背包中物品的最大价值。

##问题解析

我们可以对物品任意地进行切分，并按照重量比例来计算相应价值。

1. 对于物品 𝑖 ，它在单位重量下的价值为 𝑣𝑎𝑙[𝑖−1]/𝑤𝑔𝑡[𝑖−1] ，简称单位价值。
2. 假设放入一部分物品 𝑖 ，重量为 𝑤 ，则背包增加的价值为 𝑤×𝑣𝑎𝑙[𝑖−1]/𝑤𝑔𝑡[𝑖−1] 。

##贪心策略选定

大化背包内物品总价值，本质上是最大化单位重量下的物品价值。

1. 将物品按照单位价值从高到低进行排序。
2. 遍历所有物品，每轮贪心地选择单位价值最高的物品。
3. 若剩余背包容量不足，则使用当前物品的一部分填满背包。

##代码实现

#python代码示例
class Item :
    def __init__(self,w,v):
        self.w = w 
        self.v = v

def fraction_knapsack(wgt,val,cap) :
    items = [Item(w,v) for w,v in zip(wgt,val)]
    
    items.sort(key = lambda x : x.v / x.w,reverse=True)
    
    res = 0
    
    for item in items :
        if item.w <= cap :
            res += item.v
            cap -= item.w
        else :
            res += (item.v / item.w) * cap 
            break
    return res 

//c++代码示例
class Item
{
	int w ;
	int v ;
	Item(int w,int v) : w(w),v(v){
	}
} ;

double fractionKnapsack(vector<int> &wgt,vector<int> &val,int cap)
{
	vector<int> items ;
	for (int i = 0 ; i < wgt.size() ; i++)
	{
		items.push_back(Item(wgt[i],val[i])) ;
	}
	
	sort(items.begin(),items.end(),[](Item &a,Item &b)
	{
		return (double)a.v/a.w > (double)b.v/b.w ;
	});
	
	double res = 0 ;
	for (auto &item : items)
	{
		if (item.w <= cap)
		{
			res = res + item.v ;
			cap = cap - item.w ;
		}
		else
		{
			res = res + (double)(item.v/item.w) * cap ;
			break ; 
		}
	}
	return res ;
	
}

##正确性验证

单位价值更大的物品总是最优选择，贪心策略一定有效。