15.2 分数背包问题¶
Question
给定 \(n\) 个物品,第 \(i\) 个物品的重量为 \(wgt[i-1]\)、价值为 \(val[i-1]\) ,和一个容量为 \(cap\) 的背包。每个物品只能选择一次,但可以选择物品的一部分,价值根据选择的重量比例计算,问在限定背包容量下背包中物品的最大价值。示例如图 15-3 所示。
图 15-3 分数背包问题的示例数据
图解 15-3:分数背包问题的示例数据
容量 50 的分数背包可以装入整件香蕉和部分菠萝,图中给出这一最优方案。
给定 5 件物品与背包容量 cap = 50,物品数据见下表。每件最多取其全部重量,也可以任意切分,只取一部分;所获价值按所取重量占原重量的比例计算。
画面左侧列出编号 i、重量 wgt[i-1]、价值 val[i-1],各行用水果图标标识物品。第 2 行香蕉和第 4 行菠萝以浅橙色突出,两条箭头分别标“放入重量 20”“放入重量 30”,指向右侧标有“背包容量 cap = 50”的背包。底部给出最优方案及最大价值算式。
下表前三列转写原图,水果名称来自图标;额外的“单位价值”列由价值除以重量算出,原图未画这一列。例如苹果的单位价值为 50 ÷ 10 = 5。
| 编号与图标 | 重量 | 价值 | 单位价值 |
|---|---|---|---|
| 1(苹果) | 10 | 50 | 5 |
| 2(香蕉) | 20 | 120 | 6 |
| 3(葡萄) | 30 | 150 | 5 |
| 4(菠萝) | 40 | 210 | 5.25 |
| 5(西瓜) | 50 | 240 | 4.8 |
整件香蕉占重 20、价值 120,剩余容量为 30;菠萝原重 40,因此只取其四分之三,得到 (30/40) × 210 = 157.5 的价值。图底的最大价值算式是 120 + (30/40) × 210 = 277.5;两者总重 20 + 30 = 50,其余物品不取。
分数背包问题和 0-1 背包问题整体上非常相似,状态包含当前物品 \(i\) 和容量 \(c\) ,目标是求限定背包容量下的最大价值。
不同点在于,本题允许只选择物品的一部分。如图 15-4 所示,我们可以对物品任意地进行切分,并按照重量比例来计算相应价值。
- 对于物品 \(i\) ,它在单位重量下的价值为 \(val[i-1] / wgt[i-1]\) ,简称单位价值。
- 假设放入一部分物品 \(i\) ,重量为 \(w\) ,则背包增加的价值为 \(w \times val[i-1] / wgt[i-1]\) 。
图 15-4 物品在单位重量下的价值
图解 15-4:物品在单位重量下的价值
单位价值等于物品价值除以重量;选取其中重量为 w 的一部分时,背包增加的价值为 w 乘以该物品的单位价值。
分数背包允许切分物品,比较每单位重量带来的价值,比只比较整件总价值更能判断应优先选谁。
画面左侧表格按原编号列出五件物品,水果名称由图标转写。第四列表头为“单位价值 val[i-1] / wgt[i-1]”,各格直接印有计算结果 5、6、5、5.25、4.8;这些数字已在原图中,并非本图解另加的列。画面右侧用所取重量 w 与单位价值相乘,表示“背包内的增加价值”。
| 编号与图标 | 重量 | 价值 | 单位价值 |
|---|---|---|---|
| 1(苹果) | 10 | 50 | 5 |
| 2(香蕉) | 20 | 120 | 6 |
| 3(葡萄) | 30 | 150 | 5 |
| 4(菠萝) | 40 | 210 | 5.25 |
| 5(西瓜) | 50 | 240 | 4.8 |
单位价值的计算如苹果 50 ÷ 10 = 5。右侧图示关系是:选取重量 w × 单位价值 val[i-1] / wgt[i-1] = 背包内的增加价值;它适用于整件和部分取用。按表比较,香蕉的单位价值最高,菠萝次之。
1. 贪心策略确定¶
最大化背包内物品总价值,本质上是最大化单位重量下的物品价值。由此便可推理出图 15-5 所示的贪心策略。
- 将物品按照单位价值从高到低进行排序。
- 遍历所有物品,每轮贪心地选择单位价值最高的物品。
- 若剩余背包容量不足,则使用当前物品的一部分填满背包。
图 15-5 分数背包问题的贪心策略
图解 15-5:分数背包问题的贪心策略
按单位价值从高到低排列物品,优先用单位价值更高的物品填充背包。
最大化限定容量下的背包总价值,本质上是让每一单位背包容量尽可能装入单位价值最高的物品。因此,分数背包的贪心策略需要先对所有候选物品按单位价值降序排序。
中央表格按单位价值降序重排,四列的编号、重量、价值和单位价值数字均已画在原图中,水果名称由图标转写。图中两处说明分别为“根据单位价值从高到低排序”和“贪心策略:优先选择单位价值更高的物品”。右侧灰色箭头向上指向单位价值更高的方向;实际取用顺序从表格顶部向下。
下表保留原图顺序。苹果与葡萄的单位价值同为 5,图中苹果在前;相等的单位价值不要求固定的先后顺序。
| 编号与图标 | 重量 | 价值 | 单位价值 |
|---|---|---|---|
| 2(香蕉) | 20 | 120 | 6 |
| 4(菠萝) | 40 | 210 | 5.25 |
| 1(苹果) | 10 | 50 | 5 |
| 3(葡萄) | 30 | 150 | 5 |
| 5(西瓜) | 50 | 240 | 4.8 |
遍历时尽量取完整件物品;剩余容量不足时,只切取能填满背包的一部分。套用前文容量 50 的示例,会先取整件香蕉,再取重量 30 的菠萝,得到 277.5;这是结合前文的说明,本图只画了排序与选择规则。
2. 代码实现¶
我们建立了一个物品类 Item ,以便将物品按照单位价值进行排序。循环进行贪心选择,当背包已满时跳出并返回解:
class Item:
"""物品"""
def __init__(self, w: int, v: int):
self.w = w # 物品重量
self.v = v # 物品价值
def fractional_knapsack(wgt: list[int], val: list[int], cap: int) -> int:
"""分数背包:贪心"""
# 创建物品列表,包含两个属性:重量、价值
items = [Item(w, v) for w, v in zip(wgt, val)]
# 按照单位价值 item.v / item.w 从高到低进行排序
items.sort(key=lambda item: item.v / item.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
/* 物品 */
class Item {
public:
int w; // 物品重量
int v; // 物品价值
Item(int w, int v) : w(w), v(v) {
}
};
/* 分数背包:贪心 */
double fractionalKnapsack(vector<int> &wgt, vector<int> &val, int cap) {
// 创建物品列表,包含两个属性:重量、价值
vector<Item> items;
for (int i = 0; i < wgt.size(); i++) {
items.push_back(Item(wgt[i], val[i]));
}
// 按照单位价值 item.v / item.w 从高到低进行排序
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 += item.v;
cap -= item.w;
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += (double)item.v / item.w * cap;
// 已无剩余容量,因此跳出循环
break;
}
}
return res;
}
/* 物品 */
class Item {
int w; // 物品重量
int v; // 物品价值
public Item(int w, int v) {
this.w = w;
this.v = v;
}
}
/* 分数背包:贪心 */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
// 创建物品列表,包含两个属性:重量、价值
Item[] items = new Item[wgt.length];
for (int i = 0; i < wgt.length; i++) {
items[i] = new Item(wgt[i], val[i]);
}
// 按照单位价值 item.v / item.w 从高到低进行排序
Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
// 循环贪心选择
double res = 0;
for (Item item : items) {
if (item.w <= cap) {
// 若剩余容量充足,则将当前物品整个装进背包
res += item.v;
cap -= item.w;
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += (double) item.v / item.w * cap;
// 已无剩余容量,因此跳出循环
break;
}
}
return res;
}
/* 物品 */
class Item(int w, int v) {
public int w = w; // 物品重量
public int v = v; // 物品价值
}
/* 分数背包:贪心 */
double FractionalKnapsack(int[] wgt, int[] val, int cap) {
// 创建物品列表,包含两个属性:重量、价值
Item[] items = new Item[wgt.Length];
for (int i = 0; i < wgt.Length; i++) {
items[i] = new Item(wgt[i], val[i]);
}
// 按照单位价值 item.v / item.w 从高到低进行排序
Array.Sort(items, (x, y) => (y.v / y.w).CompareTo(x.v / x.w));
// 循环贪心选择
double res = 0;
foreach (Item item in items) {
if (item.w <= cap) {
// 若剩余容量充足,则将当前物品整个装进背包
res += item.v;
cap -= item.w;
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += (double)item.v / item.w * cap;
// 已无剩余容量,因此跳出循环
break;
}
}
return res;
}
/* 物品 */
type Item struct {
w int // 物品重量
v int // 物品价值
}
/* 分数背包:贪心 */
func fractionalKnapsack(wgt []int, val []int, cap int) float64 {
// 创建物品列表,包含两个属性:重量、价值
items := make([]Item, len(wgt))
for i := 0; i < len(wgt); i++ {
items[i] = Item{wgt[i], val[i]}
}
// 按照单位价值 item.v / item.w 从高到低进行排序
sort.Slice(items, func(i, j int) bool {
return float64(items[i].v)/float64(items[i].w) > float64(items[j].v)/float64(items[j].w)
})
// 循环贪心选择
res := 0.0
for _, item := range items {
if item.w <= cap {
// 若剩余容量充足,则将当前物品整个装进背包
res += float64(item.v)
cap -= item.w
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += float64(item.v) / float64(item.w) * float64(cap)
// 已无剩余容量,因此跳出循环
break
}
}
return res
}
/* 物品 */
class Item {
var w: Int // 物品重量
var v: Int // 物品价值
init(w: Int, v: Int) {
self.w = w
self.v = v
}
}
/* 分数背包:贪心 */
func fractionalKnapsack(wgt: [Int], val: [Int], cap: Int) -> Double {
// 创建物品列表,包含两个属性:重量、价值
var items = zip(wgt, val).map { Item(w: $0, v: $1) }
// 按照单位价值 item.v / item.w 从高到低进行排序
items.sort { -(Double($0.v) / Double($0.w)) < -(Double($1.v) / Double($1.w)) }
// 循环贪心选择
var res = 0.0
var cap = cap
for item in items {
if item.w <= cap {
// 若剩余容量充足,则将当前物品整个装进背包
res += Double(item.v)
cap -= item.w
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += Double(item.v) / Double(item.w) * Double(cap)
// 已无剩余容量,因此跳出循环
break
}
}
return res
}
/* 物品 */
class Item {
constructor(w, v) {
this.w = w; // 物品重量
this.v = v; // 物品价值
}
}
/* 分数背包:贪心 */
function fractionalKnapsack(wgt, val, cap) {
// 创建物品列表,包含两个属性:重量、价值
const items = wgt.map((w, i) => new Item(w, val[i]));
// 按照单位价值 item.v / item.w 从高到低进行排序
items.sort((a, b) => b.v / b.w - a.v / a.w);
// 循环贪心选择
let res = 0;
for (const item of items) {
if (item.w <= cap) {
// 若剩余容量充足,则将当前物品整个装进背包
res += item.v;
cap -= item.w;
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += (item.v / item.w) * cap;
// 已无剩余容量,因此跳出循环
break;
}
}
return res;
}
/* 物品 */
class Item {
w: number; // 物品重量
v: number; // 物品价值
constructor(w: number, v: number) {
this.w = w;
this.v = v;
}
}
/* 分数背包:贪心 */
function fractionalKnapsack(wgt: number[], val: number[], cap: number): number {
// 创建物品列表,包含两个属性:重量、价值
const items: Item[] = wgt.map((w, i) => new Item(w, val[i]));
// 按照单位价值 item.v / item.w 从高到低进行排序
items.sort((a, b) => b.v / b.w - a.v / a.w);
// 循环贪心选择
let res = 0;
for (const item of items) {
if (item.w <= cap) {
// 若剩余容量充足,则将当前物品整个装进背包
res += item.v;
cap -= item.w;
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += (item.v / item.w) * cap;
// 已无剩余容量,因此跳出循环
break;
}
}
return res;
}
/* 物品 */
class Item {
int w; // 物品重量
int v; // 物品价值
Item(this.w, this.v);
}
/* 分数背包:贪心 */
double fractionalKnapsack(List<int> wgt, List<int> val, int cap) {
// 创建物品列表,包含两个属性:重量、价值
List<Item> items = List.generate(wgt.length, (i) => Item(wgt[i], val[i]));
// 按照单位价值 item.v / item.w 从高到低进行排序
items.sort((a, b) => (b.v / b.w).compareTo(a.v / a.w));
// 循环贪心选择
double res = 0;
for (Item item in items) {
if (item.w <= cap) {
// 若剩余容量充足,则将当前物品整个装进背包
res += item.v;
cap -= item.w;
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += item.v / item.w * cap;
// 已无剩余容量,因此跳出循环
break;
}
}
return res;
}
/* 物品 */
struct Item {
w: i32, // 物品重量
v: i32, // 物品价值
}
impl Item {
fn new(w: i32, v: i32) -> Self {
Self { w, v }
}
}
/* 分数背包:贪心 */
fn fractional_knapsack(wgt: &[i32], val: &[i32], mut cap: i32) -> f64 {
// 创建物品列表,包含两个属性:重量、价值
let mut items = wgt
.iter()
.zip(val.iter())
.map(|(&w, &v)| Item::new(w, v))
.collect::<Vec<Item>>();
// 按照单位价值 item.v / item.w 从高到低进行排序
items.sort_by(|a, b| {
(b.v as f64 / b.w as f64)
.partial_cmp(&(a.v as f64 / a.w as f64))
.unwrap()
});
// 循环贪心选择
let mut res = 0.0;
for item in &items {
if item.w <= cap {
// 若剩余容量充足,则将当前物品整个装进背包
res += item.v as f64;
cap -= item.w;
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += item.v as f64 / item.w as f64 * cap as f64;
// 已无剩余容量,因此跳出循环
break;
}
}
res
}
/* 物品 */
typedef struct {
int w; // 物品重量
int v; // 物品价值
} Item;
/* 分数背包:贪心 */
float fractionalKnapsack(int wgt[], int val[], int itemCount, int cap) {
// 创建物品列表,包含两个属性:重量、价值
Item *items = malloc(sizeof(Item) * itemCount);
for (int i = 0; i < itemCount; i++) {
items[i] = (Item){.w = wgt[i], .v = val[i]};
}
// 按照单位价值 item.v / item.w 从高到低进行排序
qsort(items, (size_t)itemCount, sizeof(Item), sortByValueDensity);
// 循环贪心选择
float res = 0.0;
for (int i = 0; i < itemCount; i++) {
if (items[i].w <= cap) {
// 若剩余容量充足,则将当前物品整个装进背包
res += items[i].v;
cap -= items[i].w;
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += (float)cap / items[i].w * items[i].v;
cap = 0;
break;
}
}
free(items);
return res;
}
/* 物品 */
class Item(
val w: Int, // 物品
val v: Int // 物品价值
)
/* 分数背包:贪心 */
fun fractionalKnapsack(wgt: IntArray, _val: IntArray, c: Int): Double {
// 创建物品列表,包含两个属性:重量、价值
var cap = c
val items = arrayOfNulls<Item>(wgt.size)
for (i in wgt.indices) {
items[i] = Item(wgt[i], _val[i])
}
// 按照单位价值 item.v / item.w 从高到低进行排序
items.sortBy { item: Item? -> -(item!!.v.toDouble() / item.w) }
// 循环贪心选择
var res = 0.0
for (item in items) {
if (item!!.w <= cap) {
// 若剩余容量充足,则将当前物品整个装进背包
res += item.v
cap -= item.w
} else {
// 若剩余容量不足,则将当前物品的一部分装进背包
res += item.v.toDouble() / item.w * cap
// 已无剩余容量,因此跳出循环
break
}
}
return res
}
### 物品 ###
class Item
attr_accessor :w # 物品重量
attr_accessor :v # 物品价值
def initialize(w, v)
@w = w
@v = v
end
end
### 分数背包:贪心 ###
def fractional_knapsack(wgt, val, cap)
# 创建物品列表,包含两个属性:重量,价值
items = wgt.each_with_index.map { |w, i| Item.new(w, val[i]) }
# 按照单位价值 item.v / item.w 从高到低进行排序
items.sort! { |a, b| (b.v.to_f / b.w) <=> (a.v.to_f / a.w) }
# 循环贪心选择
res = 0
for item in items
if item.w <= cap
# 若剩余容量充足,则将当前物品整个装进背包
res += item.v
cap -= item.w
else
# 若剩余容量不足,则将当前物品的一部分装进背包
res += (item.v.to_f / item.w) * cap
# 已无剩余容量,因此跳出循环
break
end
end
res
end
可视化运行
内置排序算法的时间复杂度通常为 \(O(n \log n)\) ,空间复杂度通常为 \(O(\log n)\) 或 \(O(n)\) ,取决于编程语言的具体实现。
除排序之外,在最差情况下,需要遍历整个物品列表,因此时间复杂度为 \(O(n)\) ,其中 \(n\) 为物品数量。
由于初始化了一个 Item 对象列表,因此空间复杂度为 \(O(n)\) 。
3. 正确性证明¶
采用反证法。假设物品 \(x\) 是单位价值最高的物品,使用某算法求得最大价值为 res ,但该解中不包含物品 \(x\) 。
现在从背包中拿出单位重量的任意物品,并替换为单位重量的物品 \(x\) 。由于物品 \(x\) 的单位价值最高,因此替换后的总价值一定大于 res 。这与 res 是最优解矛盾,说明最优解中必须包含物品 \(x\) 。
对于该解中的其他物品,我们也可以构建出上述矛盾。总而言之,单位价值更大的物品总是更优选择,这说明贪心策略是有效的。
如图 15-6 所示,如果将物品重量和物品单位价值分别看作一张二维图表的横轴和纵轴,则分数背包问题可转化为“求在有限横轴区间下围成的最大面积”。这个类比可以帮助我们从几何角度理解贪心策略的有效性。
图 15-6 分数背包问题的几何表示
图解 15-6:分数背包问题的几何表示
用矩形宽度表示重量、高度表示单位价值,面积表示价值,直观展示有限容量应优先选取哪些物品。
分数背包允许分割并只取物品的一部分,所获价值按所取重量的比例计算。背包容量为 50;由于“价值 = 重量 × 单位价值”,图中以矩形宽度表示物品重量、高度表示单位价值,矩形面积便对应物品价值。
图中五个矩形紧邻排列,按高度从左向右递减;水果图标对应的名称、原编号、宽度和高度见下表。横轴下方的双向箭头标出背包容量 50,覆盖最左侧香蕉的整个宽度,并延伸到第二个矩形(菠萝)内部。
图面直接标注矩形宽度、高度及容量 50。下表中的整件价值、所取重量和价值由这些标注推算,原编号沿用前文物品表;原图没有另写总价值 277.5。
| 物品(原编号) | 重量/矩形宽 | 单位价值/矩形高 | 整件价值 | 所取重量 | 所取价值 |
|---|---|---|---|---|---|
| 香蕉(2) | 20 | 6 | 120 | 20 | 120 |
| 菠萝(4) | 40 | 5.25 | 210 | 30 | 157.5 |
| 苹果(1) | 10 | 5 | 50 | 0 | 0 |
| 葡萄(3) | 30 | 5 | 150 | 0 | 0 |
| 西瓜(5) | 50 | 4.8 | 240 | 0 | 0 |
容量 50 先被香蕉占去 20,余下 30 只能取菠萝宽度 40 的四分之三,留下重量 10 未取;后续三个矩形不进入容量区间。所取总面积为 20 × 6 + 30 × 5.25 = 277.5,对应最大总价值。