算法学习笔记（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 = vdef 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 = 0for item in items :if item.w <= cap :res += item.vcap -= item.welse :res += (item.v / item.w) * cap breakreturn 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 ;}

##正确性验证

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