DevTang | 唐巧修改

2026-03-08 22:37:28

很多人以为，只要开了 梯子，自己的真实 IP 就完全隐藏了。

但实际上，在很多浏览器里，你的 真实 IP 仍然可能被网站看到。

原因可能是：WebRTC。

什么是 WebRTC

WebRTC 是浏览器里的一个实时通信技术，用于：

• 视频会议
• 语音聊天
• P2P 文件传输

为了建立点对点连接，浏览器会主动检测你的网络信息，例如：

• 公网 IP
• 局域网 IP
• NAT 网络结构

问题在于：

WebRTC 的网络请求有时候不会走代理，而是直接从本地网络发出。

这就导致一个情况：

即使你开启了 梯子，网站仍然可能获取到你的 真实 IP 地址。

如何检测自己是否泄露 IP

可以打开这个网站检测：

https://browserleaks.com/webrtc

如果页面出现类似提示：

• WebRTC exposes your Local IP
• WebRTC IP doesn’t match your Remote IP

说明你的浏览器 存在 WebRTC IP 泄露。

最简单的解决方案

解决方法其实非常简单：
限制 WebRTC 只通过代理连接。

在 Chrome / Edge 浏览器里安装官方插件：

WebRTC Network Limiter

安装地址：

https://chrome.google.com/webstore/detail/webrtc-network-limiter/npeicpdbkakmehahjeeohfdhnlpdklia

安装之后：

让 WebRTC 流量也走代理，从而避免真实 IP 泄露。设置方法见下图：

一句话总结

很多人开了 梯子，但 WebRTC 仍然可能泄露真实 IP。

最简单的解决办法就是：

安装 WebRTC Network Limiter，让所有 WebRTC 流量走代理。

这样你的浏览器隐私保护才算真正完整。

其它

除了 WebRTC 外，IPv6 也可能是泄露点，检测链接是：https://browserleaks.com/ip，解决方案是开启 IPv6 相关的代理。

2026-03-01 22:45:25

今天尝试安装了一下 OpenClaw，记录一些要点。

1、执行安装脚本

curl -fsSL https://openclaw.ai/install.sh | bash

2、申请 Telegram Bot

在 Telegram 上找 @BotFather 聊天，输入 /newbot，然后设置好昵称和帐号名，最终记录下 Bot 的 API Key。

我本来还申请了飞书的 Bot，但是发现比 Telegram 麻烦很多，为了快速测试，就放弃了飞书。

3、申请大模型的 API Key

我申请的是 OpenRouter 上的 Key，这样方便切换模型做测试。这一步需要刷信用卡充值。

因为是测试，为了防止 OpenClaw 超用量，我充了 10 美元，并且设置了一天使用限额最多 5 美元。

4、配置

第一步安装到最后就会自动执行 openclaw onboard，这是一个交互式配置程序，然后你就可以在程序中配置上面第 2 和第 3 步的 Key。

安装好的 OpenClaw 在 ~/.openclaw/ 下有一个叫 openclaw.json的文件。所有的交互配置都是在帮你更新这个文件。

所以，其实你也可以直接在这个文件中设置 Telegram 的配置信息，类似这样：

1
2
3
4
5
6
7
8
9
10

{
  channels: {
    telegram: {
      enabled: true,
      botToken: "填写你申请的 BOT 的 KEY",
      dmPolicy: "pairing",
      groups: { "*": { requireMention: true } },
    },
  },
}

5、配对

用你的 Telegram 给 BOT 发一条信息，然后 OpenClaw 会回复你 Pairing code。在你的命令行中执行回复内容的最后一行代码，类似这样：

1

openclaw pairing approve telegram <pairing code>

，就完成了帐号的配对。

这其实修改的是 ~/.openclaw/credentials/telegram-default-allowFrom.json 文件。

所有的配置都在文件中，所以也很方便你随时查看、修改或备份。

6、控制面板

现在你就可以和 OpenClaw 用 Telegram 聊天了。你也可以打开网页版的控制面板，默认在 http://127.0.0.1:18789/ 查看到相关的信息。

7、其它的一些执令

• 关闭 openclaw：openclaw gateway stop
• 重启 openclaw：openclaw gateway restart
• 检查：openclaw doctor

8、初步的使用感受

• 定时执令应该会比较好用。比如帮你每天整理一些消息、新闻什么的。
• 当作 ifttt 的高级版应该也会挺好，比如：
  • 当我 push 文章到 github 的时候，就帮我同步发布。
  • 当我给它发票的时候，就帮我提报销（或至少整理发票）。
• 日常问答/编程/整理文件/写作 感觉都不太适合，还不如用对应的产品。
• 如果不是程序员/产品经理，就别试用了，大量的命令行操作，还是太不适合小白了。

2026-02-10 22:46:37

你是否经常在午饭后感到困倦、脑子转不动？是否明明吃了很多甜食，却依然觉得“细胞在挨饿”？

我就有这样的困扰。而且我爸爸，奶奶都有糖尿病、高血压，加上我有高尿酸，所以我一直有在关注血糖相关的知识。

最近读完了一本深度改变我饮食观的书——《控糖革命》。作者杰西·安佐佩斯（Jessie Inchauspé）通过科学的角度揭示了一个核心真相：比起计算卡路里，控制“血糖峰值”才是维持健康、保持身材和延缓衰老的关键。

以下是我整理的本书精华，带你重新认识身体里的“糖”。

一、 溯源：植物是如何“造糖”的？

在进入控糖技巧前，我们先看大自然的魔法。植物通过光合作用产生葡萄糖，并根据需要将其转化为三种形态：

1. 淀粉：葡萄糖的储存形态。
2. 纤维：虽然人类无法消化，但它是肠道的守护者，能极大缓冲糖分的吸收。
3. 果糖：比葡萄糖甜2.3倍，是植物吸引动物吃下果实，从而散播种子的诱饵。

正是这些形态的不同，决定了食物进入人体后不同的“命运”。

二、 血糖峰值：身体隐形的“杀手”

人体摄入糖分后，血糖会升高再降下，形成一个“波峰”。这个峰值越高，对身体的伤害就越大。

当血糖剧烈波动时，身体会陷入以下困境：

• 氧化应激：产生大量自由基，攻击细胞，诱发心脏病、二型糖尿病及认知下降。
• 糖化反应：糖分与蛋白质结合产生AGEs（糖化终产物），这是皮肤松弛、长皱纹、暗沉发黄的元凶。果糖的糖化速度是葡萄糖的 10 倍。
• 线粒体“罢工”：细胞忙于处理过载的葡萄糖，无法有效转化能量，导致你出现“晕碳”和疲劳感。

三、脂肪的秘密：为什么果糖更容易胖？

人体处理葡萄糖的过程如下：

• 肝脏转化：葡萄糖在经过肝脏时会转化为糖原，肝脏以此形态储存一部分葡萄糖
• 肌肉储存：我们的肌肉也可以储存糖原形态的葡萄糖
• 转化为脂肪：如果在肝脏和肌肉储存完糖原后，体内还有更多的葡萄糖，就需要把它转化成脂肪，储存在肝脏或肌肉中

但果糖更加霸道：它无法转化为糖原储存，唯一的去处就是直接转化成脂肪。这就是为什么甜食（含果糖）比单纯的面食（只含葡萄糖）更容易让人发胖的原因。

此外，高频率的血糖峰值会导致胰岛素抵抗。只有在胰岛素水平较低时，身体才能有效燃烧脂肪。

四、 9个实操技巧，平滑你的血糖曲线

控制血糖不代表要戒绝一切，而是要讲究“策略”，书中介绍了许多控糖技巧，我整理如下：

1. 调整饮食顺序（核心技巧）：按照 纤维（蔬菜）→ 蛋白质/脂肪 → 淀粉/糖的顺序进食。纤维像在小肠铺了一层滤网，能有效减缓糖分的吸收。
2. 餐前先吃点蔬菜：作为开胃菜，提前建立纤维屏障。
3. 停止死磕卡路里：100 卡路里的果糖和 100 卡路里的蛋白质对身体的代谢影响完全不同。
4. 打造“控糖早餐”：早餐要有蛋白质和纤维，拒绝高碳水和果汁（打碎的水果失去了纤维阻挡）。
5. 警惕代糖：阿斯巴甜、麦芽糖醇等会误导胰岛素分泌；如果非要用代糖，建议选择赤藓糖醇、罗汉果甜苷或甜叶菊。
6. 餐后吃甜点，而非单独吃：有正餐垫底，糖分吸收会更慢。
7. 餐前喝点醋：醋酸能暂时抑制淀粉酶活性，减缓转化速度。推荐用油醋汁代替酸奶酱。
8. 餐后动一动：哪怕只是散步，也能帮助肌肉消耗掉多余的葡萄糖。
9. 给甜食找个“伴”：吃甜食时，搭配点坚果（蛋白质）或蔬菜（纤维），能平滑血糖曲线。

五、结语

《控糖革命》带给我们的最大启发是：健康的身体，不在于极端的节食，而在于对代谢规律的尊重。

当你学会通过调整进食顺序、利用纤维和醋等简单工具来抚平血糖波动，你会发现：精力变好了，皮肤亮了，甚至连身材也自然而然地轻盈了。

从下一餐开始，先吃那盘蔬菜吧！

2026-01-29 09:51:36

这是本系列的第 2 篇，主题是：不懂不投。

我们刚开始投资理财的时候，通常会寻求以下这些方法来找到投资标的。

常见的错误办法

1、问朋友。我们通常会问那些看起来投资理财收益比较高的朋友，问他们应该买什么股票。
对于朋友推荐的股票，我们通常会“无脑”买入。但如果有一天，股票突然大幅回撤，我们通常就会陷入恐慌。我们会怀疑：这个朋友到底靠不靠谱？他之前赚钱是靠运气，还是因为现在判断出了问题？接着，我们就会陷入各种猜忌、焦虑和紧张中，最后甚至睡不着觉。如果股票持续下跌，我们甚至可能割肉离场。所以说，跟着朋友买其实并不那么靠谱。

2、看走势。我们可能会去看某些股票或基金的历史走势。看到它在过去三年或五年涨得很好，我们就买入。这也是理财 App 或者某些理财经理推荐的首选理由：它过去 X 年涨幅 XX，排名 XX。

但这很容易陷入“价值陷阱”，比如：

1. 周期性误判：有些股票仅仅是在某个周期内表现优秀。比如房地产在过去十年涨得很好，但这并非因为单体公司有多好，而是因为当时整个大环境让所有房企都很赚钱。如果你仅仅因为过去业绩好而买入，一旦遭遇经济下滑或泡沫破裂，就会面临巨大的损失。

2. 均值回归陷阱：很多股票或基金某年表现出色，仅仅是因为那一年的风格与它匹配。所有行业都有“大小年”之分，未来遇到“小年”时，表现自然就会变差。我把这叫做“均值回归”。

这就好比考试：你的平均水平可能是第三名。发挥好的时候能考第一名，发挥不好则可能掉到第五名，但你始终是在第三名上下徘徊。

很多基金经理或股票的表现也是在自身价值上下震荡。如果你在高点买入，在回撤时就会损失惨重，甚至被深套。

3、跟风。跟风是 A 股散户的常见操作，某个时间什么热，就跟风买什么，涨了就快速卖掉，主打一个击鼓传花，赌谁是最后接盘的大傻子。

这种情况下，我们假设你的胜率是 50%。每次获胜挣 20%，每次赌失败亏 20%。如果你进行了 10 次这样的操作，那你整体的收益期望就是 (1.2^5)*(0.8^5)=0.82,所以你折腾了半天，最后 1 块钱的本金变成了 0.82 元。

当然，如果有人认为自己跟风总是赢，这也是有可能的，但是因为自己不敢长期持有，只要涨一点点就卖，其实每次挣的是一点点收益。但是如果偶尔遇到亏损的时候，自己舍不得卖掉，就会一次亏很多。做这种短线操作的人，需要极强的止损纪律，大部分人也是很难做到的。

不懂不投

所以回到股票投资，我觉得投资理财一定要自己懂才行。如果你完全不懂或一知半解，这些都会成为你的陷阱。因为：

1. 心理层面：不懂的人往往“拿不住”。当股票大幅下跌时，无论是否割肉，你都会极度焦虑、睡不好觉，担心本金损失。
2. 投资层面：如果你懂，面对下跌说不定还能逆势加仓；即便不加仓，至少能睡个好觉。

此外，世界上还有很多投资陷阱。有些人甚至专门为“制造陷阱”而生，比如搞资金盘、割韭菜或传销。这些行为有些是非法的，有些则游走在法律边缘。如果大家没有能力分辨这些陷阱，很容易就在投资理财中遭遇严重的亏损。

小结

小结一下，常见的错误投资：

• 问朋友。其实本质上信的是朋友的业绩，朋友如果业绩下滑，就会怀疑。
• 看走势。其实本质上是用过去业绩替代未来判断，不靠谱。
• 跟风。纯投机，50% 胜率下期望是负的。

心理层面，只有懂了，才可能拿得住，睡得着觉。

另外，真正懂也可以避免很多骗局。

以上。

2026-01-24 08:20:53

序言

我打算系统性整理一下这几年投学习投资理财的心得。因为一方面通过总结，可以让自己进一步加深对投资的理解。另一方面我也想分享给同样想学习理财的读者们。

我的女儿虽然还在读小学，但我也给她报了一个针对小学生的财商课。她对理财非常有兴趣，我也想通过这一系列的文章，给她分享她爸爸的理财成长经历。

这是本系列的第 1 篇，主题是每个人必须自己懂理财。

我身边的案例

我是 80 年代出生的，不得不说，我所处的是那个年代是缺乏理财和财商教育的。因此，我发现我身边的人大多不具备优秀的理财能力。

下面我举几个身边朋友的真实例子。

朋友 A：

他都把挣到的钱存银行定期或者余额宝。但是在现在这个年代，收益率是非常低的，只有一点几。但是他非常胆小，怕买其他的产品会导致亏损，所以说不敢碰。

朋友 B：

朋友 B 买了很多基金。但是他胆子很小，每个只买 1000 - 5000 块钱。然后账户里面有着几十只基金。既看不过来，也不知道应该如何操作。

唯一好的一面是：不管任何行业有行情，他都有一只基金命中。这让他的错失恐惧症（FOMO）小了很多。

朋友 C：

我这个朋友之前在快手上班，在 P2P 盛行的年代，把自己的所有积蓄都投在 P2P 上，最后爆雷，损失惨重。

朋友 D：

这个朋友通过另外一个朋友了解到有一个股票正在做庄阶段，未来会大涨，于是就听信买入，最后损失了 90%。

朋友 E：

朋友 E 的大学同学有一个在香港卖保险，于是听朋友的推荐在香港买了很多保险。但是过了 5 年，他发现收益率和最初承诺的相差非常大。这个时候看合同才发现，合同上写的收益测算并不保证。但是现在赎回的话，只能拿到非常少的本金，所以他只能继续硬着头皮每年交钱。

只有理解才能有效持有

听完上面几个朋友的故事，你身边有类似的朋友吗？

我跟一些朋友交流，我问他们，你们为什么不自己先学习投资理财的知识，之后再去做相关的操作呢？他们很多回答说，这个事情太专业了，专业的事情交给专业的人做就可以了。

当我反问他们：假如你买了一个专业人士管理的基金，那你对他的信仰来自于哪呢？你其实对他每个月发的报告并没有完全的判断能力，你只能选择相信他。

大多数时候，你其实相信的是他过去的业绩。如果它连续三年、连续五年一直都盈利，或者有超额收益，你就会持续持有它，甚至买入更多。

如果它连续几年亏损或者某一年大额亏损，你就会质疑它，甚至赎回它。

你的信心其实就是来源于过去的业绩表现。那这和散户的追涨杀跌有什么本质区别呢？

在你持仓持续下跌的那些时间，你能睡好觉吗？如果你不能理解它，那显然不能。

所以我说，每个人必须懂投资理财。

只有你深刻理解了你买入的是什么，才能在它下跌的时候有信心继续持有它，甚至抄底，才能睡得着觉。

小结

每个人都必须懂理财。因为银行的定期存款利率太低，而其他理财产品都需要深刻理解，才可能做到长期持有。

另外，社会上充斥着像 P2P 一类的产品，以及宣传这类产品的巧舌如簧的销售。他们不断地诱惑着我们，如果我们没有辨识能力，也可能将自己辛苦一辈子挣到的钱损失掉。

以上。

2026-01-11 22:41:29

引言

背包问题是动态规划中的经典问题，也是 GESP 六级必考的知识点。其原理虽然需要花一些时间，但大多数孩子都能掌握，但是到了具体的题目时，因为背包问题变化较多，就不那么容易写出代码来。

本文将试图把背包问题的各种考法都列举出来，帮助大家巩固练习。

背包问题

背包问题之所以叫这个名字，是因为其背景故事是：往一个容量有限的背包里面，放入一些物品。每个物品有不同的体积大小，所以会占用相应的背包的容量。物品不能被分割，所以要么整个放入背包中，要么不放入。我们需要找出放入背包的价值最大的方案。

举一个简单的例子，背包容量是 10L：

• 物品 1：体积 7 L，价值 8
• 物品 2：体积 5 L，价值 5
• 物品 3：体积 4 L，价值 4

虽然物品 1 的价值最大，价值/体积(即单位体积的价值)也最大，但是因为放入物品 1 之后，剩余的空间 3L 无法再放入别的物品而浪费掉了。就不如不放物品 1，而放入物品 2 和物品 3 带来的总价值大。

由此我们也能看出，背包问题不能用简单的贪心来解决，而需要用动态规划。

解题思路

背包问题的转移方程可以被优化为一维，但为了方便理解，我们先看没有优化的版本。我们定义：

• 每个元素的体积为 a[i]，价值为 v[i]。
• dp[i][j] 表示用前 i 个物品，放入容量为 j 的背包时，所能达到的最大价值

那对于第 i 个物品，如果我们已经知道了前面的结果，那么我们有两种选择：

• 不放入 第 i 个物品，这样 dp[i][j] = dp[i-1][j]
• 放入 第 i 个物品，这样 dp[i][j] = dp[i-1][j-a[i]] + v[i]

而以上就是状态转移方程，我们在上面两种情况下取最优的情况：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]] + v[i]) 。

另外我们需要考虑一下初始化的情况，即 dp[0][1~n] 应该怎么赋值。因为前 0 个物品什么都没选，那么价值肯定都是 0，所以让它们都等于 0 即可。

将以上逻辑写成代码如下：

1
2
3
4
5
6
7

memset(dp, 0, sizeof dp);
for (int i = 1; i <= 3; ++i)
    for (int j = 1; j <= 10; ++j) {
        dp[i][j] = dp[i-1][j];
        if (j-a[i]>=0)
            dp[i][j] = max(dp[i][j], dp[i-1][j-a[i]] + v[i]);
    }

在这段代码中，为了保证 j-a[i] 的值为正，加了一个 if 来检查，保证没有下标越界的代码。如果下标越界，有可能会读取到随机值，也可能读取到非法地址，造成运行异常（Runtime Error）。

我们再用刚刚的例子来做一下表格演示：背包容量是 10L。

• 物品 1：体积 7 L，价值 8
• 物品 2：体积 5 L，价值 5
• 物品 3：体积 4 L，价值 4

经过转移方程的计算，最终，我们可以填出下面这个二维表格，表格中的每一项都计算出来了用前 i 个物品，体积为 j 时的最优化方案。这也是符合动态规划的最优子结构的特征。

01 背包

所谓的 01 背包，就是指物品的数量只有 1 个，只有选与不选两种方案。刚刚的例子就是一个 01 背包的例子。

我们发现 dp[i][j] 只与两个值相关 dp[i-1][j] 和 dp[i-1][j-a[i]]，这样的二维数组利用的效率很低。所以，我们就想到，能不能把第 i 维省略掉，这样可以节省存储空间（但没有节省运算时间）。

压缩后的代码如下：

1
2
3
4
5

memset(dp, 0, sizeof dp);
for (int i = 1; i <= 3; ++i)
    for (int j = 10; j >= a[i]; --j) {
        dp[j] = max(dp[j], dp[j-a[i]] + v[i]);
    }

我们注意到，j 的循环方式从正序变成了逆序。之所以要这么操作，读者可以用表格的方式，把正着循环的结果填一下就能明白。

如果 j 不是倒着循环，在一轮 j 的循环过程中，dp[j] 的值会在修改后，再一次被访问到，这样就会使得一个物品实际上已经计算了放入的价值，又被重复计算第二次。

完全背包

一个物品被多次重复放入和重复计算价值，其实是我们在完全背包问题中需要的效果。所以，刚刚的代码，如果我们把 j 正序循环，就是完全背包的代码，如下所示：

1
2
3
4
5

memset(dp, 0, sizeof dp);
for (int i = 1; i <= 3; ++i)
    for (int j = a[i]; j <= 10; ++j) {
        dp[j] = max(dp[j], dp[j-a[i]] + v[i]);
    }

但是为了方便理解，我们还是把完全背包的非压维代码也一并看一下：

1
2
3
4
5
6
7
8
9

memset(dp, 0, sizeof dp);
for (int i = 1; i <= 3; ++i)
    for (int j = 1; j <= 10; ++j) {
        dp[i][j] = dp[i-1][j];
        if (j-a[i]>=0) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-a[i]] + v[i]);
            dp[i][j] = max(dp[i][j], dp[i][j-a[i]] + v[i]);
        }
    }

因为 dp[i][j-a[i]] >= dp[i-1][j-a[i]]，所以以上代码可以省略成：

1
2
3
4
5
6
7
8

memset(dp, 0, sizeof dp);
for (int i = 1; i <= 3; ++i)
    for (int j = 1; j <= 10; ++j) {
        dp[i][j] = dp[i-1][j];
        if (j-a[i]>=0) {
            dp[i][j] = max(dp[i][j], dp[i][j-a[i]] + v[i]);
        }
    }

我们可以记住这个写法，因为后面有一些题因为各种情况可能无法压维，就会需要这种写法。

我们还是用刚刚的例子来填写二维表格，背包容量是 10L。物品数量改为无限。

• 物品 1：体积 7 L，价值 8
• 物品 2：体积 5 L，价值 5
• 物品 3：体积 4 L，价值 4

以下是填写出来的值：

题目变为完全背包后，可以看到最后答案变了，最优方案变成了放入两个物品 2，得到最大价值 10。

学习完以上内容后，可以让学生练习以下两道题：

以下是更多的背包基础练习题：

多重背包

多重背包描述了这样一种场景，一个物品将同时受两个限制条件的制约，例如：一个背包，即有体积限制，又有重量限制，让你往里放物品，求最大化物品价值的放法。

P1794 装备运输 就是多重背包的一道典型例题，在题目中，每件武器有体积和重量两个限制条件。

对于多重背包，我们同样用前 i 个物品来划分阶段：

• dp[i][j] 表示 i 体积 j 重量下的最大火力。
• 转移方程：dp[i][j] = max(dp[i][j], dp[i-v[k]][j-g[k]] + t[k]);

同理，如果物品的数量是无限的，则正着 for，如果物品的数量是有限的，则倒着 for。

P1794 装备运输 的参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <bits/stdc++.h>
using namespace std;

int V, G, N, dp[510][510], v[510], g[510], t[510];

int main() {
    cin >> V >> G >> N;
    for (int i = 1; i <= N; ++i)
        cin >> t[i] >> v[i] >> g[i];
    for (int k = 1; k <= N; ++k)
        for (int i = V; i>= v[k]; i--)
            for (int j = G; j >= g[k]; j--)
                dp[i][j] = max(dp[i][j], dp[i-v[k]][j-g[k]] + t[k]);
    cout << dp[V][G];
    return 0;
}

如果把 01 背包和完全背包想像成填一个一维的表格，那么多重背包就在填一个二维的表格。我们需要保证表格的填写过程符合动态规划的阶段性，表格总是从一个方向往另一个方向填，填过的数字不会再次被修改（在没压维的情况下），这样才能保证状态无后效性。

动态规划题目能够划分出清晰的阶段，后一个阶段只依赖于前面的阶段，问题就解决了一大部分。

可供练习的题目如下：

背包变型一：物品的相互依赖

P1064 金明的预算方案 描述了一种背包问题的变型：在此题中，物品不是简单的 1 个或多个，而是分为主件或附件，每个主件可以有 0 个、1 个或 2 个附件。

应该如何表示这种复杂的物品关系呢？其实，我们可以把物品的每种组合都枚举出来，因为附件数量最多为 2 个，所以情况就可以枚举出以下情况：

• 不选主件（当然也就没有附件）
• 选主件，不选附件
• 选主件+附件 1
• 选主件+附件 2
• 选主件+附件 1+附件 2

于是，我们就可以在处理主件的时候，把以上几种情况都比较一下，选最优的方案。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int m;
    int w;
    int t;
};

int n, m;
vector<Node> va;
vector<vector<Node> > vb;
int dp[40000];

void updateDP(int i, int m, int w) {
    if (i-m >= 0) {
        dp[i] = max(dp[i], dp[i-m] + w);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    va.resize(m);
    vb.resize(m);
    for (int i = 0; i < m; ++i) {
        Node node;
        scanf("%d%d%d", &node.m, &node.w, &node.t);
        node.w = node.w*node.m; 
        va[i] = node;
        if (node.t != 0) {
            vb[node.t - 1].push_back(node);
        }
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < m; ++i) {
        // 只处理主件，附件与主体一并处理
        if (va[i].t == 0) {
            for (int j = n; j > 0; j--) {
                // 选主件，不选附件
                updateDP(j, va[i].m,va[i].w);
                // 选主件+附件 1
                if (vb[i].size() > 0) {
                    int money = va[i].m + vb[i][0].m;
                    int weight = va[i].w + vb[i][0].w;
                    updateDP(j, money, weight);
                }
                // 选主件+附件 2
                if (vb[i].size() == 2) {
                    int money = va[i].m + vb[i][1].m;
                    int weight = va[i].w + vb[i][1].w;
                    updateDP(j , money, weight);
                }
                // 选主件+附件 1+附件 2
                if (vb[i].size() == 2) {
                    int money = va[i].m + vb[i][0].m + vb[i][1].m;
                    int weight = va[i].w + vb[i][0].w + vb[i][1].w;
                    updateDP(j, money, weight);
                }
            }   
        }
    }
    cout << dp[n] << endl;
    return 0;
}

背包变型二：求最小值

有些时候，我们不是求背包能够装的物品的最大价值，而是求最小价值。例如 B3873 小杨买饮料 这题，此题我们可以把饮料的容量当作背包的容量，把饮料的价格当作价值，但是此题相对于标准的背包问题有两个变化：

• 1、题目希望求最小的费用，相当于背包所装的物品价值需要最低。
• 2、题目给定的背包容量不固定，而是“不低于 L”。

针对以上的变化，我们的状态定义虽然不变，用 dp[i][j] 表示前 i 种饮料在 j 容量下的最小价值，但是状态转移变成了：
dp[i][j] = min(dp[i-1][j-l[i]] + c[i], dp[i-1][j])

在这种情况下，初始的第 0 种饮料什么都喝的值为 0，即：dp[0][0] = 0。

但是其它的值就不能设置成 0 了，如果设置成 0，那么任何情况下 dp[i][j]就已经是最小的值了，就不能被更新了。我们需要把 dp[i][j]默认的值设置成“无穷大”，这样才可能更新出有意义的值。

在设置无穷大这件事情上，有一个使用 memset 的技巧，即：memset(dp, 0x7f, sizeof dp);，此技巧将每个字节都填充成了二进制的 01111111（即 0x7f），因为最高为是符号位，所以保留成 0。这种 memset 技巧虽然初始化的值比 INT_MAX 略小一点，但是写起来更快，另外在进行加法运算的时候，也不用担心结果溢出成负数。

以上方案解决了变化一。我们再来看变化二。

变化二使得答案不一定在 dp[i][L]，因为答案不一定是刚好 L 升，所以要取 L ~ L+max(l[i]) 这一段范围。这样就解决了变化二。

最后我们用滚动数组压维，然后因为是 01 背包（每个饮料只能选一次），我们压维之后需要倒着 for 循环背包大小。

以下是参考代码，代码中用 STL 的 min_element 来求最小值，读者也可以参考这种写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/**
 * 01 背包问题的变化
 * 
 * 假设第 i 种饮料的费用是 c[i], 容量是 l[i]
 * dp[i][j] 表示用前 i 种饮料，凑成 j 升的最小费用。
 * 
 * 则，转移方程为：
 *  - dp[i][j] = min( dp[i-1][j-l[i]] + c[i] , dp[i-1][j] ) 
 * 
 * 因为 i 只与 i-1 相关，所以这一层可以压缩。转移方式优化为：
 *  - dp[j] = min(dp[j- l[i]] + c[i], dp[j])
 * 
 * 初使化：
 *  - dp[0] = 0;
 *  - dp[1-L] = memset(0x7f)
 * 
 * 其它：
 *  - 倒着 dp，因为每种饮料只能用一次
 *  - 最大值检查了一下，不会超 int，就不用 long long 了
 *  - 因为答案不一定是刚好 L 升，所以要取 L ~ L+max(l[i]) 这一段范围
 *  - 因为是取最小值，所以初使化设置成 0x7f7f7f7f（接近 21 亿，但是又没到 INT_MAX），
 *    这样运算不会超 int，又可以是较大值
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int dp[1010000], c[550], l[550], N, L, maxL;

int main() {
    ios::sync_with_stdio(0);       
    cin >> N >> L;
    for (int i = 0; i < N; ++i) {
        cin >> c[i] >> l[i];
        maxL = max(maxL, l[i]);
    }
    maxL += L;
    memset(dp, 0x7f, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = maxL; j - l[i] >= 0; --j) {
            dp[j] = min(dp[j], dp[j - l[i]] + c[i]);
        }
    }
    // 因为答案不一定是刚好 L 升，所以要取 L ~ L+max(l[i]) 这一段范围
    int ans = *min_element(dp+L, dp+maxL+1);
    if (ans == 0x7f7f7f7f) cout << "no solution" << endl;
    else cout << ans << endl;

    return 0;
}

以上代码虽然解决了问题，但是还有一点不完美，就是 dp 数组实在太大了。有没有可能 dp 数组更小呢？我们可以想到，因为每种饮料的价格都是正数，所以，如果有一个答案是超过 2*L 升的情况，同时它的价格极低，这种情况下，我们的答案就是只喝这一种饮料。不会出现超过 2*L 升，我们还叠加喝了两种饮料的情况。

我们可以反证：假如有一个答案是喝两种饮料，总容量超过 2*L 升，那么必定有一个饮料的容量是大于等于 L 升的。那么，我们只喝那个大于等于 L 升的饮料，肯定总价格更低。

所以，我们的优化方案就是：我们只需要把 dp 数组的大小开到 2*L 即 4000 即可（题目规定 L 最大为 2000）。在此优化方案下，我们再特判一下每个大于 L 升的饮料，看是不是更便宜。

以下是参考代码，时间和空间复杂度都更优：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <bits/stdc++.h>
using namespace std;

int dp[4100], c[550], l[550], N, L;

int main() {
    ios::sync_with_stdio(0);       
    cin >> N >> L;
    for (int i = 0; i < N; ++i) {
        cin >> c[i] >> l[i];
    }
    memset(dp, 0x7f, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 4000; j - l[i] >= 0; --j) {
            dp[j] = min(dp[j], dp[j - l[i]] + c[i]);
        }
    }
    int ans = *min_element(dp+L, dp+4000);
    // 如果单个饮料就可以超 L，则判断一下
    for (int i = 0; i < N; ++i)
        if (l[i] >= L) 
            ans = min(ans, c[i]);

    if (ans == 0x7f7f7f7f) cout << "no solution" << endl;
    else cout << ans << endl;

    return 0;
}

小结：对于求最小值的背包问题，除了 dp[0][0] = 0 外，我们需要把别的初始值设置为 0x7f，以保证递推求 min 的过程中，每个 dp 数组值可以得到更新。

相关的练习题目还有：

• P2918 Buying Hay S
• P1679 神奇的四次方数

背包变型三：求平均值

有一类题，虽然看着不像是背包问题，但是最后可以抽象成背包问题。而且，他们背包大小都是 sum/2。

P2392 考前临时抱佛脚 就是一道典型的例题。

在此题中，每一科的复习都可以看成两个并行的任务，而任务最短的时间就是让一个任务的时间尽可能接近 sum/2。这样，我们就可以把 sum/2 当成背包的容量，把每道题的价值和体积看成相等即可。

因为在本题中，sum 最大值为 20*60 = 1200，所以背包大小最大是 600 即可。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/**
此题可以用动态规划，也可以用搜索，因为每科只有最多 20 个题目，所以搜索空间最大是 2^20 等于约 100 万。

用动态规划解题时，此题可以把每次复习看作一次 01 背包的选择。每道题的价值和成本相同。背包的目标是尽可能接近 sum/2，因为sum 最大值为 `20*60 = 1200`，所以背包大小最大是 600。
 */
#include <bits/stdc++.h>
using namespace std;

int s[4], v[25], ans, dp[610];

int dpAns(int n) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += v[i];
    }
    int m = cnt / 2;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++i) {
        for (int j = m; j>=v[i]; --j) {
            dp[j] = max(dp[j], dp[j-v[i]] + v[i]);
        }
    }
    int ret = max(dp[m], cnt - dp[m]);
    return ret;
}

int main() {
    scanf("%d%d%d%d", s, s+1, s+2, s+3);
    for (int i = 0; i < 4; ++i) {
        memset(v, 0, sizeof(v));
        for (int j = 0; j < s[i]; ++j) {
            scanf("%d", v+j);   
        }
        ans += dpAns(s[i]);
    }
    printf("%d\n", ans);
    return 0;
}

相关的练习：

背包变型四：计数

有一类背包问题，不是问你最大的价值，而是问你相关的计数。

例如：P1832 A+B Problem 就是其中的典型例题。

要解此题，我们可以先把质数算出来保存下来，接下来，我们需要用背包的思路，对表格进行计数:

• dp[i][j] 表示用前 i 个质数组成 j 一共的可能数
• 转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]] + dp[i-1][j-a[i]*2]...

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * 解法：
 *  - 无穷背包
 *  - 先把质数算出来，保存在数组里面
 * 
 * dp[i][j] 表示用前 i 个质数组成 j 一共的可能数
 * dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]] + dp[i-1][j-a[i]*2]...
 * 
 * 初始化：dp[0][0] = 1
 * 
 * 注意：答案需要用 long long 保存。
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1010

int a[200];
long long dp[200][MAXN];

bool isPrime(int a) {
    for (int i = 2; i*i<=a; ++i)
        if (a%i == 0) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; ++i)
        if (isPrime(i)) 
            a[++a[0]] = i;     

    dp[0][0] = 1;
    for (int i = 1; i <= a[0]; ++i) // 第 i 个质数 a[i]
        for (int j = 0; j<= n; ++j) { // 组成 j 这个值
            for (int p = j; p >= 0; p -= a[i]) { // 完全背包，试着放 0-n 个 a[i]
                dp[i][j] += dp[i-1][p];
            }
        }

    cout << dp[a[0]][n] << endl;
    return 0;
}

背包变型五：负数体积

有一些题目，元素的体积会是负数。

P13018 调味平衡 就是一道典型的例题。它也是 GESP 202506 七级题目。

第一种解法（空间占用过大）

用上面提到的计数类的方法。

dp[i][j][k] 表示前 i 种食材，达到酸度 j，甜度 k 是否可能。

dp[i][j][k] = dp[i-1][j-a[i]][k-b[i]] 是否可能。

把 i 这一层简化dp[j][k] = dp[j - a[i]][k - b[i]]

初始化：dp[0][0] = 1

但是以上的方法时间和空间消耗(500000x500000)太大。

正确的解法

考虑到可以把一种食材的酸度和甜度求差，得出酸和甜的差值。如果两种食材的差值加起来为零，则刚好酸度=甜度。

这样就可以把 dp 简化。

• dp[j]表示前 i 种食材的酸甜度差值 j 是否存在，如果存在，其值为酸甜度的和。
• dp[j] = dp[j - dif[i]] + a[i] + b[i]

相当于背包元素的体积变成了差值，价值变成了 a[i] + b[i]。

因为 dif[i] 有正有负，所以为了保证值不会覆盖，我又恢复成二维的 dp：

• dp[i][j] 表示前 i 种食物，凑成 j 的酸甜度差的最大和。

因为 j 可能为负值，所以我们把平衡点设置成 50000（可以想像成刚开始差值就是 50000，求最后差值不变）

这样 j 中间最多从 50000 减成 0（因为每个食材差值最大为 500，最多有 100 个食材），所以不会变成负数。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/* 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN int(100*500+10)

int dp[110][MAXN*2], n, a, b, c, d;

int main() {
    ios::sync_with_stdio(0);    
    cin >> n;
    memset(dp, 0x8f, sizeof dp);
    dp[0][50000] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a >> b;
        c = a-b;
        d = a+b;
        for (int j = 0; j <= 50000*2; j++)
            if (j-c >= 0)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-c] + d);    
    }
    cout << dp[n][50000] << endl;
    return 0;
}

相关练习题目

除了以上的变化，更多变化的练习：