01背包 这个算法界的守门员

🌳一个写全栈技术、偏底层基建、爱研究 bug 的程序员博客。技术界的一名小工匠⊥⊤，每天进步一点点。

背包问题可以说是算法经典中的经典，动态规划算法中经典中的经典。

01背包仅是背包问题的一个个例，背包还有完全背包、分组背包等，其他都是01背包的一个变体、改造、叠加组合。这里只研究这个经典的01背包。

01背包虽用暴力穷举可以实现最大价值的求取，但随着数据的增大，它直接会卡死机，因为穷举的时间复杂度是O(2的n次方)，太慢了，所以这里采取dp[][]表格的方式来做，时间复杂度为O(n*m)，要快的多。

01背包问题的描述

现有1个背包容量(容重量、容体积均可)为V，有n件物品(各物品容量、价值分别表示为w、v)，每件物品只选或不选。求：在背包可容纳的范围内，可选到的物品组合的最大价值。

附：01表示一件物品选或者不选它。

动态规划思路

动态规划法的一个算法思路，它的思路是通过将大问题拆解为小问题，通过在小问题上求最优解的方式，最终达到在整体大问题上求出最优解。

编码实现及细节说明

测试用例的数据：

物品objs
weight value
w v
2 6
3 5
4 7

//// Created by Lenovo on 2026/6/20.//#include<stdio.h>#defineMAX_N100#defineMAX_V100// dp[i][j]：前i个物品，背包容量j的最大价值intdp[MAX_N][MAX_V];intw[MAX_N],v[MAX_N];// 重量、价值intmain(){intn,V;// 输入物品数、背包容量(容纳重量)scanf("%d%d",&n,&V);for(inti=1;i<=n;i++){scanf("%d%d",&w[i],&v[i]);}// 动态规划for(inti=1;i<=n;i++){for(intj=1;j<=V;j++){if(j<w[i]){// 装不下当前物品dp[i][j]=dp[i-1][j];}else{// 不选 / 选 取最大值if(dp[i-1][j]>dp[i-1][j-w[i]]+v[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=dp[i-1][j-w[i]]+v[i];}printf("------\n");}}printf("%d\n",dp[n][V]);return0;}

程序运行结果：

D:\CLionProjects\argorithm\algorithm\01pg2arr.exe310263547------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------18Process finished withexitcode0

算法复杂度

1. 时间复杂度
   两层循环：外层遍历n件物品，内层遍历背包容量V
   总运算次数：n * V
   时间复杂度：O(nV)

2. 空间复杂度
   开辟 n行V列二维数组，存储所有子问题结果
   空间复杂度：O(nV)

初次接触的坑点

1.很多初次接触这个01背包动态规划法的程序员、编程爱好者、学生等，会习惯性的代入或使用暴力穷举的思考方式求解(而不自知)，这也是本文作者初次接触时的现状(后面才反思到)。心想只要把所有组合例出来，再取最大值不就行了吗。

暴力穷举在数据量小时勉强可以，但数据量超过一定量级，效率极慢了，100个、1万个、10万个呢，它的时间复杂度是O(2的n次方)。

举个例子：
n=100，V=1000
DP运算次数：100 * 1000 = 10 万次，计算机瞬间跑完；
暴力 2^{100} 等则是天文数字，完全无法计算，甚至宕机。

动态规划法与暴力穷举法完全不是一个思路，所以会觉得懵逼了。

2.不理解为什么要用二维DP数组[][]
怎么存不用纠结。一维的也可以只不过要加一些辅助存储。二维的也可以，二维[][]这种表示形式像表格，易于理解。动态规划算法的这个思想是不娈的，只要能实现通过子优解得到整体最优解就行。建议自行系统的补习算法思想基础。

动动手做做表格，逐步填数据推演一遍，就明白它的简单巧妙了。状态转换方程这4行，下边代码块中ifelse这4行，这几行是重点，吃透了，这个01背包就吃透了，便算是学会了。

// 动态规划for(inti=1;i<=n;i++){for(intj=1;j<=V;j++){if(j<w[i]){// 装不下当前物品dp[i][j]=dp[i-1][j];}else{// 不选 / 选 取最大值if(dp[i-1][j]>dp[i-1][j-w[i]]+v[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=dp[i-1][j-w[i]]+v[i];}printf("------\n");}}

重点理解这一句，码测千遍其意自现。
dp[i][j] = dp[i-1][j - w[i]] + v[i];

下篇见，goodbye。