什么时候必须换成 DP
第 1 步：包能装 10，三件东西 第 2 步：每斤最值钱的是甲，先拿 第 3 步：剩 4 斤，乙丙都放不下 第 4 步：其实拿乙和丙更值钱 甲 乙 丙 重 值 6 30 5 20 5 20 一个问题必须用 DP 而不能用贪心，是因为【0】
装不下的背包贪心和最优
背包能装 10，三件物品（重量, 价值）是 (6,30)(5,20)(5,20)，每件要么整件拿走要么不拿。 运行下面这段程序： #include <algorithm> #include <iostream> #i
能切开就不一样了
还是这三件、还是装 10，但这次可以切开按比例拿（切下来那部分的价值按 价值 × 剩余容量 ÷ 重量 算，保证整除）。 运行下面这段程序： #include <algorithm> #include <iostream&g
写 0-1 背包的贪心
补全 knap_greedy：按每斤价值从高到低排（用 denser），装得下就整件拿走。输出总价值。 （本题用 g++ -std=c++17 -O0 编译。）
写 0-1 背包的动态规划
补全 knap_dp：dp[c] 表示容量 c 时的最大价值，每件物品容量从大往小更新一遍。输出最大价值。 （本题用 g++ -std=c++17 -O0 编译。）
写可以切开的背包
补全 knap_frac：同样按每斤价值排，装得下就整件拿，装不下就切一块把包填满（切下来的价值用 it.v * cap / it.w）。 （本题用 g++ -std=c++17 -O0 编译。）
三个数摆在一起看
同一批物品、同一个容量，一次输出三个数：0-1 贪心 / 0-1 最优 / 可切开的贪心。 （本题用 g++ -std=c++17 -O0 编译。）
交换论证在证明什么（C++）
交换论证要说明的是【0】。
交换论证的一步怎么走
第 1 步：任务耗时 4 1 3 2 第 2 步：前两个是一处逆序 第 3 步：把它俩换过来 第 4 步：后面的人完成时刻不变 第 5 步：只有换到前面的人提早了 4 1 3 2 交换论证的每一步是【0】。
把一处逆序换过来
四个任务耗时 4、1、3、2，前两个是一处逆序（大的排在小的前面）。把它俩换过来，看总等待时间的变化。 运行下面这段程序： #include <algorithm> #include <iostream> #incl