【狂热算法篇】完全背包异次元冒险：容量魔法觉醒，价值风暴来袭！
欢迎拜访：羑悻的小杀马特.-ZEEKLOG博客
本篇主题：轻轻松松拿捏完全背包问题呀！！！
制作日期：2026.03.04
隶属专栏：美妙的算法世界
目录
家人们，你有个容量有限的背包去 “淘宝”。仓库里宝贝无数，各有重量和价值，咋装能让背包里宝贝价值总和最高？这就是完全背包问题！
一·问题定义：
这里还没学习到 01背包问题的小伙伴可以看一看博主的这篇文章；绝对通俗易懂；传送门：
【动态规划篇】01 背包的逆袭：如何用算法装满你的 “财富背包”_01背包问题-ZEEKLOG博客
完全背包问题是经典的组合优化问题，属于背包问题的一个变种。
给定一组物品，每种物品都有对应的重量W 、价值V ，同时有一个容量为 C 的背包。与 0 - 1 背包（每种物品仅有一个，只能选择放入或不放入背包）不同，完全背包中每种物品的数量是无限的，可选择放入背包任意次。目标是在不超过背包容量的限制下，挑选物品放入背包，使得背包内物品的总价值达到最大。
二·具体问题演示：
假设你是一位准备去冒险的勇士，你有一个容量为 10 的背包，面前有三种魔法道具可供挑选，每种道具可以拿任意多个。具体信息如下：
你需要思考如何选择道具放入背包，才能让背包内道具的总价值最大，这就是一个典型的完全背包问题。
三·动态规划解答完全背包：
当然了这类题和我们之前讲的01背包一样用的是动态规划；具体区别就是状态转移方程有点不同结合了数学归纳化简法等这里的化简法和我们的通配符匹配这篇很像大家可以去学一学：传送门：
【动态规划篇】正则表达式与通配符：开启代码匹配的赛博奇幻之旅-ZEEKLOG博客
无非就是动归的那几步：
那么下面我们以一道模版题从非装满和装满状态来分析一下如何实现：
测试用例：
题目传送门：
3.1非装满状态：
3.1.1状态定义：
这里我们和01背包的定义相差不大：
dp[i][j]表示在0到i个物品中选择使得总体积不超过j情况下最大价值。
3.1.2状态转移方程：
这里我们把问题变成对i位置的物品选多少次即可；下面请看图：
状态转移方程：
dp[i][j]=max{ dp[i-1][j-nv[i]]+nw[i] }(n>=0)
如果直接这样写，那么就是n^3时间复杂度了；因此利用数学归纳法给它化简一下：
因此得出方程：
3.1.3初始化：
这里我们还是选择多开一行多开一列；然后根据定义分析一下那一行一列如何填充：
比如第0行即 在0个物品中选不超过j(>=0)因此肯定是无法选择即最大价值就是0；其次就是列：可以选多个物品；但是背包最大容量是0；故不选：最大价值也是0；利用vector特性可以选择不初始化。
3.1.4返回值：
根据状态方程定义直接返回dp[n][V]即可。
3.1.5填充dp表：
填表顺序还是从上往下从左往右（从状态转移方程可看出）
这里就根据我们的状态转移方程即可；此时就需要特判一下防止下标越界，其次就是注意下标映射关系即可：
first代表体积 second代表价值：
dp[i][j] = max(dp[i - 1][j], j - bag[i - 1].first >= 0 ? dp[i][j - bag[i - 1].first] + bag[i - 1].second : 0);3.1.6非装满状态代码总结：
int n, V; int main() { cin >> n >> V; vector<pair<int, int>> bag(n);//体积——价值 for (int i = 0; i < n; i++) cin >> bag[i].first >> bag[i].second; //////ans1: vector<vector<int>> dp(n + 1, vector<int>(V + 1)); //注意下标映射关系 for (int i = 1; i <= n; i++) for (int j = 1; j <= V; j++) //防止越界如果越界即不能用第二个直接置为0 dp[i][j] = max(dp[i - 1][j], j - bag[i - 1].first >= 0 ? dp[i][j - bag[i - 1].first] + bag[i - 1].second : 0); cout << dp[n][V] << endl; }3.1.7非装满状态滚动数组降维优化：
这里还是老套路和01背包那里一样；走那三步：
1·去掉有关i的下标：二维变一维。
2·确定好j的遍历方式。
3·从哪遍历或者遍历到哪。
为什么走这三步或者原理是啥请看01背包篇：传送门：
【动态规划篇】01 背包的逆袭：如何用算法装满你的 “财富背包”_01背包问题-ZEEKLOG博客
这里需要和01背包区别开的就是第二三步了：
我们先看状态转移方程：
这里发现我们每次用到的是上面的值以及它左边的；因此就和01背包不同了；我们遍历填充dp的时候是从左往右（而01背包的优化是从右往左）；其次就是我们如果要用后面选大于0的状态j必须大于等于v[i]；如果不用即这个位置直接套用的i-1时候填的（即不变）；-->故可以让j直接从v[i]开始即可。
代码书写：
cin >> n >> V; vector<pair<int, int>> bag(n);//体积——价值 for (int i = 0; i < n; i++) cin >> bag[i].first >> bag[i].second; //////ans1: vector<int> dp(V + 1); //注意下标映射关系 for (int i = 1; i <= n; i++) for (int j = bag[i - 1].first ; j <= V; j++) //防止越界如果越界即不能用第二个直接置为0 dp[j] = max(dp[j],dp[j - bag[i - 1].first] + bag[i - 1].second ); cout << dp[V] << endl;3.2装满状态：
对于装满状态来说；其实与非装满状态十分相似；因此下面我们就简单说一下吧：
下面就在非装满状态稍加改动即可：
3.2.1状态定义：
dp[i][j]表示在0到i个物品中选择使得总体积等于j情况下最大价值。
3.2.2状态转移方程：
这里我们只是当遍历到i位置的时候必须选择的是让它装满的状态；因为dp表中肯定存在不装满的情况；我们规定-1就是不可装满；而对于状态方程和非装满一样（只不过它代表的意义又分为了装满了和没有装满也就是非-1和-1）：
因此，如果后者是不能装满也就是-1然后加上w可能干扰dp此时的填充因此需要特判一下；
可能会有个疑问：前者dp[i-1][j]需不需要特判呢？其实也可以但是可以省略：
下面还是四种情况：
1·前面能装满后面不能：即肯定此时的dp就是前者了。
2· 前面不能装满后面能：取后者。
3·前面能装满后面能：即取最大。
4·前面不能装满后面不能： 此时直接是前者-1即可。
这里我们就发现了只特判后者即可（当然了如果我们设置其他值作为不能装满的标识就不要判断了；后面滚动数组优化会讲解）。
3.2.3初始化：
这里初始化也和上面不同；因为存在非装满情况：
3.2.4返回值：
这里返回值就要注意了；我们存在非装满情况此时的价值应该是0；如果此时dp[n][V]如果是-1；也就是最后遍历到结尾是无法装满的故返回0；其他就是dp原值。
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl; 3.2.5 填充dp表：
和上面的非装满一样；只是多了一个判断是否是非装满状态的条件而已：
for (int i = 1; i <= n; i++) for (int j = 1; j <= V; j++) //装满只是多了一个是否能装满的条件；符合全部的条件就用否则不用直接置-1；这里第一个 //不选不需要特判 dp[i][j] = max(dp[i - 1][j], j - bag[i - 1].first >= 0 && dp[i][j - bag[i - 1].first] != -1 ? dp[i][j - bag[i - 1].first] + bag[i - 1].second : -1);3.2.6装满状态代码总结：
int n, V; int main() { cin >> n >> V; vector<pair<int, int>> bag(n);//体积——价值 for (int i = 0; i < n; i++) cin >> bag[i].first >> bag[i].second; vector<vector<int>> dp(n + 1, vector<int>(V + 1)); for (int k = 1; k <= V; k++) dp[0][k] = -1; for (int i = 1; i <= n; i++) for (int j = 1; j <= V; j++) //装满只是多了一个是否能装满的条件；符合全部的条件就用否则不用直接置-1；这里第一个 //不选不需要特判 dp[i][j] = max(dp[i - 1][j], j - bag[i - 1].first >= 0 && dp[i][j - bag[i - 1].first] != -1 ? dp[i][j - bag[i - 1].first] + bag[i - 1].second : -1); //返回值还需注意： cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl; }3.2.7非装满状态滚动数组降维优化：
这里我们修改一下上面二维对非装满状态的规定；因为要让非装满状态和装满状态区别开；值不能重复因此我们让-0x3f3f3f3f 来表示不能装满（题目给的值允许的情况）。
还是前提是好处是啥：这样我们填表的时候无需对上面那样的后者进行判断了（但是要注意返回值；那么下面我们就来分析一下为什么呢？）
还是会存在那四种情况：
1·前面能装满后面不能：此时的dp为一个正数。
2· 前面不能装满后面能：此时的dp为一个正数。
3·前面能装满后面能：此时的dp为一个正数。
4·前面不能装满后面不能：此时的dp值为一个很小的负数。
这说明什么？？？如果我们是-1的规定那么dp表中肯定要么是-1要么是正值（需要判断）；而此时呢；如果我们不判断直接用那么dp表中会存在很小的负数和正确的正数。到最后我们返回的时候判断让它返回正数即可。
这就省去了我们判断的过程；对于降维优化这里就不说了（和上面一样）：
for (int k = 1; k <= V; k++) dp[k] = -0x3f3f3f3f; for (int i = 1; i <= n; i++) for (int j = bag[i - 1].first ; j <= V; j++) //装满只是多了一个是否能装满的条件；符合全部的条件就用否则不用直接置-1；这里第一个 //不选不需要特判 dp[j] = max(dp[j],dp[j - bag[i - 1].first] + bag[i - 1].second); //返回值还需注意： cout << (dp[V]<0 ? 0 :dp[V]) << endl;3.3对于本题的解答：
这里需要注意的还有个点就是由于dp是全局的故第二问要清空一下：
fill(dp.begin(), dp.end(), 0); //或者 for (auto& row : dp) fill(row.begin(), row.end(), 0);二维dp解答：
#include <iostream> #include<algorithm> #include<map> #include<vector> using namespace std; int n, V; int main() { cin >> n >> V; vector<pair<int, int>> bag(n);//体积——价值 for (int i = 0; i < n; i++) cin >> bag[i].first >> bag[i].second; vector<vector<int>> dp(n + 1, vector<int>(V + 1)); //////ans1: //注意下标映射关系 for (int i = 1; i <= n; i++) for (int j = 1; j <= V; j++) //防止越界如果越界即不能用第二个直接置为0 dp[i][j] = max(dp[i - 1][j], j - bag[i - 1].first >= 0 ? dp[i][j - bag[i - 1].first] + bag[i - 1].second : 0); cout << dp[n][V] << endl; ////ans2: //刷新dp数组 for (auto& row : dp) fill(row.begin(), row.end(), 0); for (int k = 1; k <= V; k++) dp[0][k] = -1; for (int i = 1; i <= n; i++) for (int j = 1; j <= V; j++) //装满只是多了一个是否能装满的条件；符合全部的条件就用否则不用直接置-1；这里第一个 //不选不需要特判 dp[i][j] = max(dp[i - 1][j], j - bag[i - 1].first >= 0 && dp[i][j - bag[i - 1].first] != -1 ? dp[i][j - bag[i - 1].first] + bag[i - 1].second : -1); //返回值还需注意： cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl; } 一维dp解答：
#include <iostream> #include<algorithm> #include<map> #include<vector> using namespace std; int n, V; int main() { cin >> n >> V; vector<pair<int, int>> bag(n);//体积——价值 for (int i = 0; i < n; i++) cin >> bag[i].first >> bag[i].second; //////ans1: vector<int> dp(V + 1); //注意下标映射关系 for (int i = 1; i <= n; i++) for (int j = bag[i - 1].first ; j <= V; j++) //防止越界如果越界即不能用第二个直接置为0 dp[j] = max(dp[j],dp[j - bag[i - 1].first] + bag[i - 1].second ); cout << dp[V] << endl; ////ans2: //刷新dp数组 fill(dp.begin(), dp.end(), 0); for (int k = 1; k <= V; k++) dp[k] = -0x3f3f3f3f; for (int i = 1; i <= n; i++) for (int j = bag[i - 1].first ; j <= V; j++) //装满只是多了一个是否能装满的条件；符合全部的条件就用否则不用直接置-1；这里第一个 //不选不需要特判 dp[j] = max(dp[j],dp[j - bag[i - 1].first] + bag[i - 1].second); //返回值还需注意： cout << (dp[V]<0 ? 0 :dp[V]) << endl; } 随着一声清脆的声音我们也是通过了此题。
四·复杂度分析：
4.1.时间复杂度:
代码中有两层嵌套循环，外层循环遍历n种物品，内层循环遍历背包的容量 C，因此时间复杂度为 O(nC)，其中n是物品的数量,C是背包的容量。
4.2 空间复杂度:
由于使用了一个大小为 (n+1)*(C+1)的二维数组dp来保存中间结果，所以空间复杂度为O(nC)。
滚动数组优化后：
时间复杂度还是不变而空间复杂度变成O(C) 。
五·完全背包衍生例题：
下面我们从三道经典的完全背包例题带大家应用一下上面的知识：
5.1零钱兑换：
测试用例：
题目传送门：
这里我们可以认为对于完全背包转换而来：背包体积就是这里的amount（且一定要装满）；单个价值和体积就是对应coins值；最大价值就是这里coin的最小个数 。
状态定义：dp[i][j]表示从0-i区间内选择硬币使它能够凑成j的最小硬币数
下面我们就直接分析状态方程即可：
还是分为i位置处选还是不选：
1·选：又分为选1个还是多个即dp[i-1][j-coins[i-1]]+1,dp[i-1][j-2coins[i-1]]+2,.....
老样子，化简成dp[i][j-coins[i-1]]+1----->这里对于coins注意下标映射关系。
2·不选：即dp[i-1][j]。
其次就是初始化：
对于返回值：
对于状态方程：
dp[i][j]=min(dp[i-1][j],j>=coins[i-1]?dp[i][j-coins[i-1]]+1:0x3f3f3f3f);这里如果符合下标非越界要求；填充当前dp值的时候，我们可能会存在 前面dp是不能装满的状态因此可以的出结论：
非装满的dp值肯定大于等于inf；小于的一定是可以装满的（也就是正确值）
即：
return dp[n]>=0x3f3f3f3f?-1:dp[n];解答代码：
二维dp：
dp[i][j]表示从0-i区间内选择硬币使它能够凑成j的最小硬币数： 这里因为如果amount等于0；即硬币数为0即可但是还有可能无法凑成这里就规定0x3f3f3f3f为无法凑成的情况(包括比他大) int m=coins.size(); int n=amount; vector<vector<int>>dp(m+1,vector<int>(n+1)); for(int k=1;k<=n;k++)dp[0][k]=0x3f3f3f3f; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ dp[i][j]=min(dp[i-1][j],j>=coins[i-1]?dp[i][j-coins[i-1]]+1:0x3f3f3f3f); } } return dp[m][n]>=0x3f3f3f3f?-1:dp[m][n]; 一维dp：
int m=coins.size(); int n=amount; vector<int>dp(n+1); for(int k=1;k<=n;k++)dp[k]=0x3f3f3f3f; for(int i=1;i<=m;i++){ for(int j=coins[i-1];j<=n;j++){ dp[j]=min(dp[j],dp[j-coins[i-1]]+1); } } return dp[n]>=0x3f3f3f3f?-1:dp[n];5.2零钱兑换2：
测试用例：
题目传送门：
这里仍是完全背包 (装满) 体积：amount; 单个价值和体积都是：coins值；而最大价值就是我们的方案数。
但是和上面不同的是上面不能凑齐和需要0个硬币是两种状态；而这里凑不成就是0种方案。
也就是上面那道题会有三种状态；而这道只有两种。
状态定义：
dp[i][j]表示从0-i区间内选择硬币让它能凑成j的方法数
状态方程表示：
即：
初始化：
这里就比上面简单了；因为不会存在不能满而另外标识的情况；故直接dp表默认都是0即可。
返回值：
直接返回dp[m][n]即可。
代码总结：
小细节就是注意数据范围；相加可能溢出故unsigned给它搞上。
二维dp:
int m=coins.size(); int n=amount; vector<vector<unsigned long long>>dp(m+1,vector<unsigned long long>(n+1)); for(int k=0;k<=m;k++)dp[k][0]=1; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ dp[i][j]=dp[i-1][j]+(j>=coins[i-1]?dp[i][j-coins[i-1]]:0); } } return dp[m][n];一维dp：
int m=coins.size(); int n=amount; vector<unsigned long long>dp(n+1); dp[0]=1; for(int i=1;i<=m;i++){ for(int j=coins[i-1];j<=n;j++){ dp[j]+=dp[j-coins[i-1]]; } } return dp[n]; }5.3完全平方数：
测试用例：
题目传送门：
也是完全背包（装满） 总体积：这个n；单个价值和体积：都是对应的完全平方数的值。
最大价值：我们所需要的完全平方数的最小个数。
前提是我们需要的是这个完全平方数的数组；即我们根据这个12 对应的数组是1 4 9；
这里则m就是3；即根12（强转int）;因此我们只需要遍历这个m（从1开始）然后i^2就是对应的值。 因此就更进一步转化成了我们熟悉的完全背包问题了吧！
状态定义：
dp[i][j]表示从0-i区间内选择完全平方数使得凑成j的最少数 。
状态方程表示：
只不过就是把上面的coins对应值换成i方而已：
方程即：
初始化：
返回值：
这里我们会发现无论n为多少（大于0）肯定是可以凑成的（最坏就是都是1）；因此dp表要么是0要么是inf要么是正确的值；但是只要n大于0我们返回的一定是正确的值。
解答代码：
二维dp：
dp[i][j]表示从0-i区间内选择完全平方数使得凑成j的最少数 int m=sqrt(n); const int inf=0x3f3f3f3f; vector<vector<int>>dp(m+1,vector<int>(n+1)); for(int k=1;k<=n;k++)dp[0][k]=inf; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++) dp[i][j]=min(dp[i-1][j],j-i*i>=0?dp[i][j-i*i]+1:inf); } return dp[m][n]; 一维dp：
int m=sqrt(n); const int inf=0x3f3f3f3f; vector<int>dp(n+1); for(int k=1;k<=n;k++)dp[k]=inf; for(int i=1;i<=m;i++){ for(int j=i*i;j<=n;j++) dp[j]=min(dp[j],dp[j-i*i]+1); } return dp[n];本期例题就分析到这啦；希望对大家可以建立起完全背包分析的头脑思路呀。
六.应用场景:
6.1 资源分配:
在项目管理中，假设你有一定的资金（相当于背包容量），需要购买多种设备（每种设备可购买多个），每种设备有不同的成本（相当于重量）和收益（相当于价值），目标是在资金允许的范围内获得最大的收益，这就可以转化为完全背包问题。
6.2货币找零:
给定不同面额的硬币（每种硬币数量无限）和一个要找零的金额，如何用最少的硬币数量完成找零。可以将每种硬币看作一种物品，硬币的面额看作重量，使用硬币的数量看作价值（这里目标是最小化价值），将问题转化为完全背包问题。
6.3物品组合生产:
工厂生产产品，有多种原材料，每种原材料可以无限使用，每种原材料有一定的成本和对产品的贡献值。在预算限制下，选择原材料生产产品以获得最大的总贡献值，也可以用完全背包问题来解决。
七·本篇小结：
本篇介绍了完全背包模版及相关例题应用等；不难发现完全背包和01背包【装满与非装满状态】很像；01背包传送门： 【动态规划篇】01 背包的逆袭：如何用算法装满你的 “财富背包”_01背包问题-ZEEKLOG博客
只不过是稍作改动（数学归纳化简一下）；其他简直就是非常一样。然后呢？就是滚动数组优化的时候（三步走）：对于01背包是从右往左；j遍历到某个v[i];而完全背包是从左往右；j从v[i]开始遍历。
其实博主认为这块需要注意的就是 方程的书写；条件的判断；以及滚动优化要注意的一些地方；还有初始化和返回值（注意不符合的dp值不要成为干扰项（比如装满状态时候出现的非装满的dp））
总而言之；还是按照动归的那几步来分析即可。
