#创作计划#动态规划之背包问题
2025-05-29 17:50:48
发布于：广东
141阅读
0回复
0点赞
哈喽，大家好，今天我给大家带来动态规划中的背包知识点。
点个赞吧！！！
前言
本蒟蒻是一位只有六年级的小学生，第一次写知识点类型的文章，希望各位大佬多多指点。（点个赞吧！！QVQ）
@AC君 给个精选、置顶吧！！！写这篇文章把我累成狗了好累啊！！！
好了，话不多说，现在就进入正题！！
目录
1——动态规划与背包问题
2——01背包
3——完全背包
4——多重背包
5——01背包
6——总结回顾
The first part：动态规划与背包问题
很多同学在刚开始接触动态规划时都会问：”动态规划是什么？？“，我也一样，首先让我们一起来看看动态规划的定义。
动态规划（Dynamic Programming，简称DP）是一种用于解决最优化问题和计数问题的高效算法。
实际上，动态规划就是运用了类似递推的思想，中间通过记录子问题的值从而减少重复计算，提高效率。
注意：能运用动态规划解决的题目需拥有最优子结构与无后效性。
新名词：动态转移方程，即转移（递推）时用到的式子（转移式）。
而今天的知识点——背包，就是动态规划中较为基础的一种类型。
背包，顾名思义，就是往一个像背包一样的容器内装不同体积、不同价值的东西。要使得物品体积总和不超过背包容量的情况下，最多能装多少价值的物品。
背包问题主要有三种类型：01背包、完全背包与多重背包。让我们逐一攻破！
The second part：01背包
首先看一道题目：题目
读完题目，你想到了什么？？是贪心？还是搜索？……看看接下来这几种经典错误方法中有没有你的方法：
1、按草药的价值从大到小排序
想法：价值越大，越应该取。
错误样例：
100 3
99 100
50 51
49 50
本应输出101（取后两种），但是按照这种方法会输出100 ❌
2、按采药的时间从小到大排序
想法：时间少的划算，能取更多。
错误样例：
100 3
100 100
50 49
49 50
本应输出100（取第一种），但是按照这种方法会输出99 ❌
3、按采药的”性价比“从小到大排序
想法：性价比越高（时间/价值），取到的价值肯定最大。
错误样例：
100 3
99 33
50 25
30 15
本应输出40（取后两种），但是按照这种方法会输出33 ❌
那么正解到底是什么呢？？——没错，就是背包（动态规划）
题目翻译：背包体积为T，草药数量为M，每次输入每株草药的体积t[i]与价值w[i]。
分析与解：我们设一个二维数组dp，dp[i][j]表示在当前考虑前i个物品，且背包容量为j的情况下，所能取到物品的最大价值。
接着，我们利用类似于递推的思想，推演dp[i][j]如何得到：
对于我们遇到的每一个物品，只有选与不选两种情况，
1、不选：则继承上一个物品（即考虑i-1个物品时）在背包容量为j时的最大价值和；
2、选：则继承上一个物品在背包容量为（现在背包容量-现在物品体积）的情况下，加上现在物品价值。
接着取两种情况中的最大值就可以解决这道题了。
由此，我们得到了动态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+w[i])
注：此处如果不理解，可以自己打个表试试看。
Code_1
#include<bits/stdc++.h>
using namespace std;
int T,M,t[105],w[105];
int dp[105][1005];
int main()
{
cin>>T>>M;//容量与草药株数
for(int i=1;i<=M;i++)
{
cin>>t[i]>>w[i];//体积与价值
}
for(int i=1;i<=M;i++)
{
for(int j=T;j>=0;j--)//正序倒序都可以
{
dp[i][j]=dp[i-1][j];
if(j>=t[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-t[i]]+w[i]);//要先判断是否越界
}
}
cout<<dp[M][T]<<endl;//考虑M种草药，背包容量为T时的最大价值
return 0;
}
接下来我们会发现：只需记录上一轮的情况与这一轮的情况即可，可以用滚动数组优化。
Code_2
#include<bits/stdc++.h>
using namespace std;
int T,M,t[105],w[105];
int dp[2][1005];
int main()
{
cin>>T>>M;
for(int i=1;i<=M;i++)
{
cin>>t[i]>>w[i];
}
int fg=0;
for(int i=1;i<=M;i++)
{
for(int j=T;j>=0;j--)
{
dp[fg^1][j]=dp[fg][j];
if(j>=t[i]) dp[fg^1][j]=max(dp[fg^1][j],dp[fg][j-t[i]]+w[i]);
}
fg^=1;
}
cout<<dp[fg][T]<<endl;
return 0;
}
然后我们又发现：既然都能用滚动数组优化，那难道就不能直接优化为一维的吗？
最后，我们就得到了01背包问题的模板：
Code_3
#include<bits/stdc++.h>
using namespace std;
int T,M,t[105],w[105];
int dp[1005];
int main()
{
cin>>T>>M;
for(int i=1;i<=M;i++)
{
cin>>t[i]>>w[i];
}
for(int i=1;i<=M;i++)
{
for(int j=T;j>=0;j--)//必须倒序，防止覆盖
{
if(j>=t[i]) dp[j]=max(dp[j],dp[j-t[i]]+w[i]);//省去一维
}
}
cout<<dp[T]<<endl;
return 0;
}
你学会了吗？？
更多习题：题1、题2、题3、题4
The third part：完全背包
题目
完全背包只有一点与01背包不同，就是每件物品有无数件。
此时，我们只需要将第二重循环改为正序即可。
注：此处若有不理解，可以自行打表尝试，在此我就不多赘述（千万别知道是因为我懒）
那么这道题目也就迎刃而解了。
Code_1
#include<bits/stdc++.h>
using namespace std;
int N,M,w[35],c[35];
int dp[205];
int main()
{
cin>>M>>N;
for(int i=1;i<=N;i++)
{
cin>>w[i]>>c[i];
}
for(int i=1;i<=N;i++)
{
for(int j=w[i];j<=M;j++)
{
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}
cout<<dp[M]<<endl;
return 0;
}
此处再提供一种思路，请大家自行体会（这个方法可能更好理解）
Code_2
#include<bits/stdc++.h>
using namespace std;
int N,M,w[35],c[35];
int dp[2][205];
int main()
{
cin>>M>>N;
for(int i=1;i<=N;i++)
{
cin>>w[i]>>c[i];
}
int fg=0;
for(int i=1;i<=N;i++)
{
for(int j=0;j<=M;j++)
{
dp[fg^1][j]=dp[fg][j];
if(j>=w[i])
{
dp[fg^1][j]=max(dp[fg^1][j],dp[fg][j-w[i]]+c[i]);
dp[fg^1][j]=max(dp[fg^1][j],dp[fg^1][j-w[i]]+c[i]);
}
}
fg^=1;
}
cout<<dp[fg][M]<<endl;
return 0;
}
怎么样？是不是很简单？
更多习题：题1、题2
The fourth part：多重背包
题目
多重背包的不同点在于每件物品都有对应的个数，既不是1个，也不是无数个。
对于这样的问题，我们可以在01背包的基础之上加一重循环，用变量k来枚举每一个物品所取的个数。
那么动态转移方程就是：dp[j]=max(dp[j],dp[i-1][j-w[i]*k]+v[i]*k)
Code_1
#include<bits/stdc++.h>
using namespace std;
int n,W,w[100005],v[100005],m[100005],dp[40005];
int main()
{
cin>>n>>W;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>m[i];
for(int i=1;i<=n;i++)
{
for(int j=W;j>=w[i];j--)
{
for(int k=1;k<=m[i];k++)
{
if(k*w[i]<=j) dp[j]=max(dp[j],dp[j-w[i]*k]+v[i]*k);
}
}
}
cout<<dp[W]<<endl;
return 0;
}
但是我们会发现，这道题目的数据较大，这个程序无法通过所有测试点，需要优化。
那如何进行优化呢？我们考虑采用二进制拆分的方式，将这个问题转化为01背包问题，减少遍历次数。
例如一个物品有18件，我们可以将它拆分为价值与重量都为1，2，4，8，3的五件物品，（1+2+4+8+3=18）这样就可以高效地解决这个问题了。
Code_2
#include<bits/stdc++.h>
using namespace std;
int n,W;
int v[100005],w[100005],cnt,dp[100005];
int main()
{
cin>>n>>W;
for(int i=1;i<=n;i++)
{
int vi,wi,mi;
cin>>vi>>wi>>mi;
for(int j=1;j<=mi;j*=2)
{
v[++cnt]=vi*j,w[cnt]=wi*j;
mi-=j;//二进制拆分
}
if(mi) v[++cnt]=vi*mi,w[cnt]=wi*mi;//还没拆完，剩下的数量（例如例子中的3）
}
for(int i=1;i<=cnt;i++)
{
for(int j=W;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}//01背包模板
cout<<dp[W]<<endl;
return 0;
}
所以我们就得到了多重背包的模板了。
The fifth part：总结回顾
1、三种背包的不同点：
01背包：每种物品只有1个，只有选与不选两种情况；
完全背包：每种物品有无数个，需考虑要不要取/要取几个；
多重背包：每种物品有固定的个数，需考虑取几个。
2、三种背包的共同点：
代码都较为固定，基于01背包。
3、三种背包的优化：
01背包：滚动数组、一维优化；
完全背包：滚动数组、一维优化；
多重背包：二进制优化。
结语
好了，本期的分享就到这里，“业精于勤荒于嬉，行成于思毁于随”，希望大家多多刷题，早日AC，越变越强！
最后的最后，大家点个赞吧！！
有帮助，赞一个