“01背包与优化”思想&实现
2025-06-14 21:23:55
发布于：四川
背包的思想：
背包运用的是动态规划的思想，了解的朋友可以跳过下面的一段，又或者你看不懂我下面的概述，也可以去查一查什么是动态规划思想。而且，背包问题在算法的前期只需要掌握这几个就够了。
背包所运用的动态规划思想，动态规划，字面意思，也就是动态地规划局部最优解，最后由局部最优解综合求出答案。简单点来说就是挑选出一个部分，然后枚举每一种方案，在这个部分中求取题目所规定的最优解作为局部最优解，再在局部最优解中挑选出一些组成下一部分的最优解（比如说有n种货物，每种货物有m个，每个货物有w重量与v价值，最多拿重量为k的物品，那我们就可以把这堆货物规划成n个部分，每个部分包含了挑选前i个货物的所有情况，在这里面一层一层递进求解答案。注意：每一个部分根据我上面所说的，都是由前面部分的局部最优解推过来的），以此类推，直至找到答案。
01背包：
01背包含义解释：
注：01背包，是所有背包的核心，只要掌握了它，之后的完全背包及多重背包也就迎刃而解了，所以一定要仔细学习，我也会说得细致一点。
01背包，顾名思义，每种物品只有两种情况，选与不选。一道经典的1背包题就是：有n种货物，每种货物有1个，每个货物有w重量与v价值，最多拿重量为k的物品。也不要觉得后面的完全背包与多重背包有多难，其实就是01背包的变种。
例题：
题目描述
有一个背包容量为m，还有n件物品，它们的重量分别是w1,w2...wn，它们的价值分别为v1,v2...vn,求最大总价值。
输入格式
第一行：两个整数，m（背包容量，m<=200）和n（物品数量，n<=31）
第2~n+1行：每行两个整数wi，vi，表示每个物品的重量和价值。
输出格式
仅一行，一个数，表示最大总价值。
输入样例
10 4
2 1
3 3
4 5
7 9
输出样例
12
代码&注释：
代码1：
未优化
编译器食用更佳
#include<iostream>
#include<vector>
using namespace std;
int main(){
int m,n;
cin>>m>>n;
vector<int> w(n+1);//重量
vector<int> v(n+1);//价值
vector<vector<int>> dp(n+1,vector<int>(m+1));//dp[i][j]表示在背包剩余容量为j时从下标为0到i的物品里任意取的最大价值
for(int i=1;i<=n;i++){
cin>>w[i];
cin>>v[i];
}
for(int i=1;i<=n;i++){//j<n是因为i代表物品编号，总共也就n个物品
for(int j=1;j<=m;j++){//j<m是因为j代表当前背包剩余容量，背包的最大容量也就m，不要尝试单独优化j为w[i]，这么做是错误的，会导致之后你调用大于w[i]的地方时取不到数值，也就没有办法求出正确答案。
if(j<w[i]){//当当前背包剩余容量不够装下这个物品，当前背包所装的最大价值是就是dp[i-1][j]
dp[i][j]=dp[i-1][j];//i-1代表0~i-1的物品编号,不包括i
}else{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//如果装得下物品i就比较原来的价值与装物品i的价值谁更大
}
}
}
cout<<dp[n][m];
return 0;
}
代码2：
已优化
**这里的优化的话，我觉得有必要提一嘴，这里优化是减少了一维存物品总量空间，为什么可以这么做呢？因为从代码里我们可以得知，所有的转移都是从前一层转移过来的，且是在j的左边:j-w[i]）从这里我们可以发现，之前的很多空间是浪费了的，那如何改变呢？我们不妨仔细想想为什么数据要从前一层转移过来，而不是直接使用这一层的数据呢？不就是为了不让这一层之前产生的数据迭代影响到当前的数据迭代，产生多获取物品的情况吗，如果究其原因，也是因为当循环到dp[j-w[i]]时，dp[j-w[i]]早已在这一层循环产生了改变。同时，我们再来看代码可以得知，同一层内数据改变的会在j的左边产生并被参与到同层的数据迭代只是因为j的循环方向是从左往右的！
**
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,m;
cin>>m>>n;
vector<int> w(n+1);
vector<int> v(n+1);
vector<int> dp(m+1);
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){//唯一需要理解的地方：运行顺序调换
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m];
return 0;
}
有帮助，赞一个