A背包 DP

辨析：分数背包=贪心

可分割⇒贪心 vs 整取⇒DP

本课摘要

辨析：分数背包=贪心课程回答“为什么可分割物品属于贪心而不是 01 背包”。内容以可分割⇒贪心 vs 整取⇒DP为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

判断辨析：分数背包=贪心的适用条件与状态边界
围绕“可分割⇒贪心 vs 整取⇒DP”推导转移与计算顺序
用演示、复杂度分析和配套题目校验实现

本课目录 · 0 节

正在整理目录…

先分清：这次能不能「取一部分」

前面几种背包，物品都是整件取舍，一件要么整个拿走、要么留下，没有「拿半件」这回事。可现实里有另一类物品：金粉、牛奶、汽油、矿砂……它们可以只取一部分，装满剩余空间的一小段也行。这类问题叫分数背包（也叫部分背包）。

左：整件物品（01 背包），只能整块拿或留；右：可分割物品，一整袋金粉能只舀出 0.5 袋去填满缝隙。

差别看着小，分量却很重。回想 01 背包的开头：那里我们试着用贪心（按性价比 $v/w$ 从高到低装），结果输给了 DP，因为整件取舍时，塞不下的那件只能整个放弃，贪心会在「差一点点」的地方卡住。但只要物品可以切开，这个「差一点点」就消失了：装不下整件？那就切下正好填满的一段。于是，贪心重新变成最优，而且不再需要 DP。这一页专门点破这条分界。

可切分时，贪心为什么就是最优

策略只有一句话：按单位价值 $v/w$ 从高到低装，能整件装就整件装，直到最后装不下整件的那一件，按剩余容量的比例切开，把背包填满为止。

为什么这样一定最优？关键在「可切分」赋予的自由：背包最终一定会被恰好填满（除非所有物品都装进去还有空）。既然容量必被占满，那把每一单位容量都留给单位价值最高的物品，总价值自然最大。严格一点说，用交换论证：取任一「最优」方案，若其中某一单位空间给了 $v/w$ 较低的物品，而更高性价比的物品还没装满，那就把这一单位切下来，换成高性价比那种同样一单位。空间占用不变（可切分保证换得进），而总价值只增不减（换进来的每单位价值更高）。既然任何「低 $v/w$ 抢占了本可给高 $v/w$ 的空间」的方案都能这样被改良，最优方案里就不可能存在这种错配：必被填满的每一单位，都归当前剩余里 $v/w$ 最高的物品，这恰好就是「按 $v/w$ 降序填」的贪心。

交换论证：换前那条容量条有一格错给了低性价比物品（v/w=1，虚线格），而高性价比物品（v/w=2）尚未填满；把这一格切换成高性价比的，占用不变、总价值从 9 升到 10。任何这样的错配都可被改良，故最优方案里不存在错配。

用 01 背包开头的同一组数据体会一遍：物品 $(w,v)=(2,3),(3,4),(4,5)$ ，容量 $C=8$ 。

按 v/w=1.5, 1.33, 1.25 降序：先装满 (2,3) 与 (3,4)（占 5 格、价值 7），容量还剩 3 格；最值钱但性价比最低的 (4,5) 装不下整件，切下 3/4（3 格）取价值 3.75。贪心总价值 = 10.75。

对照一下：同样这组数据若只能整取（01 背包），最优是 $(3,4)+(4,5)=9$ ，因为 $(4,5)$ 要么整件塞进去、要么彻底放弃，没法只填那 3 格的缝隙。可切分把这 $10.75-9=1.75$ 的差额补了回来。

V_{\text{greedy}}=\sum_{k}v_k \;+\; v_{\text{last}}\cdot\frac{C_{\text{rest}}}{w_{\text{last}}}

本质 · 为什么这里贪心够用、轮不到 DP

分数背包的最优子结构被「可切分」抹平了：容量必被填满，每一单位空间独立地归给单位价值最高者即可，当前最优不再牵扯后面还剩多少整数空间。于是一次排序 + 一趟扫描（ $O(n\log n)$ ）就得最优，不需要背包 DP 那张表。DP 是用来对付「整件取舍」那种牵一发动全身的耦合的，这里没有那种耦合。

跟着装一遍

把贪心用那组数据（物品 $(w,v)=(2,3),(3,4),(4,5)$ ，容量 $C=8$ ）从头装一遍，每一步只做一个动作：

排序（按 $v/w$ 降序）。 三件的单位价值是

3/2=1.5

、

4/3\approx1.33

、

5/4=1.25

，已是降序，装填顺序就定为

(2,3)\to(3,4)\to(4,5)

。背包空、累计价值 0、剩 8 格。

整件装 $(2,3)$ 。 剩 8 格

\ge

它的 2 格，整件放入：占 2 格，累计价值

0+3=3

，还剩

8-2=6

格。

整件装 $(3,4)$ 。 剩 6 格

\ge

它的 3 格，整件放入：再占 3 格，累计价值

3+4=7

，还剩

6-3=3

格。

切最后一件 $(4,5)$ 。 只剩 3 格

<

它的 4 格，装不下整件，按剩余比例切下

3/4

，取得价值

5\times\frac{3}{4}=3.75

。背包被恰好填满，总价值

7+3.75=10.75

。

下面的对照演示会把这套「排序 → 整件装 → 切尾段」实时跑给你看，并和「若整取」的 01-DP 最优并排比较。

改改看：贪心 vs 整取，两个数一起跳

下面把两条路并排算给你看：左边是可分割 → 贪心（按 $v/w$ 降序填、最后一件切开），右边是若整取 → 01-DP 最优（自写一个小背包）。改物品的 $w,v$ 或容量 $C$ ，盯住那条容量条：整件段是实心、被切开的尾段是斜纹。多数情况下贪心的数更大（切开填满了整取留下的缝隙）；当数据恰好整取就能填满时，两者持平。贪心永远 $\ge$ 整取，绝不会更差。

贪心装填：按 v/w 从高到低填，最后一件切开填满已排序

w=2 v=3

w=3 v=4

切 75%

012345678

可分割 · 贪心（本页）

10.75

按 v/w 降序、最后一件切开 · O(n log n)

若整取 · 01-DP 最优

每件整取或不取 · 需要背包 DP

可切分时，贪心多拿到 +1.75：把最值钱的那件切一部分塞满了整取时留下的缝隙。

试着把某件的

v/w

调得很高，看它被排到最前、优先整件装满；再把容量调到刚好卡在半件处，观察尾段如何被切开。

一句话分界：可分割⇒贪心，不可分割⇒背包 DP

把这一部分的整条脉络收束成一个判别动作，拿到一道「装东西求最值」的题，先问一句：物品能不能取一部分？

能切分（金粉、牛奶、汽油、按重量卖的散货）→ 按 $v/w$ 降序贪心，最后一件切开填满， $O(n\log n)$ ，用不到 DP。

整件取舍（一台机器、一本书、一件装备，只能整个拿或不拿）→ 贪心会在「差一点点」处失手，必须回到背包 DP：01 / 完全 / 多重…… 用一张表把指数级组合压成多项式。

整取时贪心的经典反例（回扣 01 背包）

就是 01 背包开头那一幕：物品 $(2,3),(3,4),(4,5)$ 、容量 8，按 $v/w$ 贪心先装 $(2,3)$ 再装 $(3,4)$ ，剩 3 格塞不下 $(4,5)$ 只得 7；最优却是 $(3,4)+(4,5)=9$ 。整取时贪心输 2，因为那 3 格的缝隙没法用「半件 $(4,5)$ 」去填。可一旦允许切分，这半件就能塞进去，反例当场消失，贪心反超到 10.75。能不能切开，就是贪心与 DP 的分水岭。

例题

P1208[USACO1.3] 混合牛奶 Mixing MilkUSACO 原生普及-

题意

要收购

n

单位牛奶，有

m

个奶农，第

i

个单价

p_i

、最多供应

a_i

单位。每个奶农的奶可以只买一部分。求凑够

n

单位的最小花费。

为什么选它（辨析对照）

这是可分割 → 贪心的教科书题，正好和 01 背包对照：物品能拆散买，于是不必做背包 DP，按单价升序，从最便宜的开始买，最后一家买够为止。它把「可切分 ⇒ 贪心」这条分界坐实成一道能提交的题。

思路 · 复杂度

按单价

p_i

升序排序，逐个奶农买「还差量」与存量的较小值

\min(r,\ a_i)

单位（

r

为尚未凑够的量），累加花费直到凑满

n

。排序

O(m\log m)

，扫描

O(m)

，纯贪心，没有 DP 表。

参考代码（贪心 · 单价升序）

C++

在洛谷打开 P1208

#include <iostream>
#include <algorithm>
using namespace std;

struct Farmer          // 一个奶农：单价 p、存量 a
{
    int p, a;
};

Farmer g[5005];

bool cmp(const Farmer &x, const Farmer &y)
{
    return x.p < y.p;               // ★按单价升序：先买最便宜的
}

int main()
{
    int n, m;                       // n 需求量，m 奶农数
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> g[i].p >> g[i].a;

    sort(g + 1, g + m + 1, cmp);    // 贪心的核心：排序

    long long cost = 0;             // 总花费
    for (int i = 1; i <= m && n > 0; i++)   // 需求没凑够就继续买
    {
        int buy = min(n, g[i].a);   // ★可只买一部分：这家最多买 min(还差多少, 存量)
        cost += (long long)buy * g[i].p;
        n -= buy;
    }

    cout << cost << endl;
    return 0;
}

练习

P1208[USACO1.3] 混合牛奶 Mixing Milk学后自测：按单价升序，逐个奶农买 min(还差量, 存量)，累加到凑满 n。确认自己能一眼判定它「可分割 ⇒ 贪心、无需 DP」。在洛谷打开

这是一节辨析课，配套的洛谷原生题只有 P1208 一道，就不用非原生题凑数了。真正要带走的是这条判别直觉：

遇到「可取一部分 / 按重量按量买」，先想贪心（按 $v/w$ 或单价排序）；遇到「整件取舍、只能整个拿或不拿」，再回背包 DP。前八节的背包 DP 是为后一种情形准备的重武器；这一节告诉你，不是所有「装背包」都要动用它。