在采购、抽奖或是游戏内资源兑换等场景里，我们常遇到一个现实约束：手里的钱或者积分固定，面前每件东西都有自己的价格和是否值得拿的属性。目标很直接，就是在不能超支的情况下，尽可能多地把东西收入囊中。这类问题在数学上可以规约为0/1背包问题的一个特例，把预算当作背包容量，单件花费当作物品重量，而每件物品对收集数量的贡献固定为1。
0/1背包的基础建模与动态规划思路
标准的0/1背包描述如下：有n件物品，第i件花费为cost[i]，在只统计件数时价值val[i]可全部取1。背包总容量为预算B。每件物品要么拿要么不拿，不能拆分，也不能重复拿。我们定义dp[i][j]表示考虑前i件物品、使用不超过j预算时能拿到的最大件数。
状态转移时，对于第i件，如果当前预算j小于cost[i]，那肯定没法拿，只能沿用之前的结果；如果j大于等于cost[i]，则可以选择拿或者不拿，取两者中较大的：不拿就是dp[i-1][j]，拿则是dp[i-1][j-cost[i]] + 1。这种递推保证了无后效性，最终答案落在dp[n][B]。由于所有val都是1，其实我们就是在数最多能装几件。
#include <iostream>
#include <vector>
using namespace std;
int maxItems(vector<int> &cost, int B) {
int n = cost.size();
// dp[i][j] 前i件在预算j下最大件数
vector<vector<int>> dp(n + 1, vector<int>(B + 1, 0));
for (int i = 1; i <= n; i++) {
int c = cost[i - 1];
for (int j = 0; j <= B; j++) {
if (j < c) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c] + 1);
}
}
}
return dp[n][B];
}
int main() {
vector<int> cost = {3, 2, 4, 1, 5};
int B = 8;
cout << maxItems(cost, B) << endl; // 输出最多能拿几件
return 0;
}
上面的代码用二维数组直观表达了递推过程。时间复杂度是O(nB)，空间是O(nB)。当预算是整数且范围不大时，这种方法既好写又稳定。但如果预算很大或者物品极多，二维数组会占用过多内存，这就需要后续的优化。
还要注意一个前提：代码里的预算B和cost都应是整数。如果原始数据是浮点金额，比如12.5元，就需要统一乘以10或者100转成整数分，否则无法作为数组下标使用。这也是实际项目里最容易踩的坑。
空间优化：滚动数组压成一维
观察转移方程会发现，dp[i][j]只依赖dp[i-1][*]这一行。因此我们完全可以用一个长度为B+1的一维数组，从后往前更新，覆盖掉旧值而不影响本次计算。关键在于内循环必须逆序遍历预算，避免同一件物品被重复选取，那就变成完全背包了。
一维写法把空间降到O(B)，在嵌入式或者大规模运算时优势明显。逻辑上和二维等价，只是把行维度隐式丢弃。下面给出改造后的版本，结构更紧凑。
def max_items(cost, B):
dp = [0] * (B + 1)
for c in cost:
# 逆序更新，防止重复拿
for j in range(B, c - 1, -1):
dp[j] = max(dp[j], dp[j - c] + 1)
return dp[B]
cost = [3, 2, 4, 1, 5]
B = 8
print(max_items(cost, B))
这段Python代码里，外层遍历每件物品，内层从B向下到c。由于j-c一定小于j，而我们是逆序走，dp[j-c]还是上一轮（即前i-1件）的值，完美符合0/1语义。如果反过来正序，就会在某件物品上累加多次。
在空间敏感的场景，比如前端小程序计算促销组合，一维DP几乎是无脑首选。它牺牲了一点可读性，换来了实打实的内存下降，并且运算速度也因缓存局部性变好而略有提升。
为什么贪心策略在这里会失效
有人可能想到：那我按花费从小到大排，依次拿最便宜的不就行了？这其实是部分背包的贪心思路。在0/1约束下，它不一定最优。因为便宜的东西凑一起可能留下无法利用的零碎预算，而稍贵但组合更紧的物品反而能塞满。
举个简单反例：预算为6，物品花费分别是3、3、4。贪心拿两个3刚好满，得2件；但如果物品是3、4、4，贪心拿一个3后剩3拿不了任何4，只拿1件，而最优其实是拿不了两个4但选一个4加别的若没有则仍1件，此处仅说明零碎问题。更极端的，预算5，花费为2、2、3，贪心拿2+2=4得2件，剩1浪费；若存在组合3+2=5也是2件，数量持平但说明贪心不保证探索全部。
| 策略 | 是否保证最多件数 | 适用条件 |
|---|---|---|
| 动态规划 | 是 | 0/1不可拆，花费整数 |
| 按价贪心 | 否 | 仅部分背包可拆分时最优 |
表格里对比得很清楚。动态规划穷举了所有子集的可能，自然能拿到理论最大值；贪心省时间却丢了最优性。所以在预算卡死且物品不可拆的业务里，别迷信排序，老老实实DP更稳。
实际工程中的小技巧
如果物品数量极多但预算中等，可以先用花费做一遍过滤，去掉那些单价超过预算的无效项。另外当多件物品花费相同时，它们等价，只需保留一件代表，因为件数贡献都是1，这能缩短n。
在Web端用JavaScript跑这类计算时，建议把预算放大系数和花费预处理放在接口层，前端只收整数数组。如下片段展示了过滤与调用：
function solve(costs, budget) {
const valid = costs.filter(c => c <= budget);
const dp = new Array(budget + 1).fill(0);
for (const c of valid) {
for (let j = budget; j >= c; j--) {
dp[j] = Math.max(dp[j], dp[j - c] + 1);
}
}
return dp[budget];
}
// 假设后台给的是元，转成分
const costs = [300, 200, 400, 100, 500].map(x => x / 100);
console.log(solve(costs, 8));
这段代码演示了前端视角的处理：过滤掉超预算项，一维DP出结果。注意map里除以100是为了贴合上文整数化示例，实际中常是乘100。工程上把这些细节封装成纯函数，方便单测和复用。
总结来看，有限预算下最大化收集数量就是0/1背包的件数最大化形态。掌握二维推演、一维压缩以及贪心误区，就能在采购系统、福利发放等模块里写出既正确又高效的代码。
0/1_knapsack动态规划budget_optimization修改时间：2026-08-02 12:06:38