题目描述
01背包：给你n个物品，每个物品都有一个体积和价值，且物品只有一个，给你一个背包体积v，要求背包里面装的物品价值之和最大。
问题求解
对于背包问题，我们都能从下面的思路进行思考： 问题中不是有n个个物件嘛，也就是从0到n个物件中找出体积小于v的最大价值。 我们分解问题，我们从0到i中找小于体积j的最大价值，不包括i，因为问题求的就是包括i的最大价值（后文表示：f(i-1，j)）. 而f(i-1,j)是可以求的，怎么求f(i,j)呢？——很简单，去掉第i件物品，那么f(i,j)就可以表示为，f(i-1,j-v[i]) w[i]——v[i]第i件物品的体积 ,w[i]第i件物品的价值。 总结： 最大价值==f(i,j)==f(i-1,j)与f(i-1,j-v[i]) w[i]相比的最大值。
牛客网01背包
代码语言：javascript复制cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int V,N;
cin>>V>>N;
vector<int> v(N 1),w(N 1);
for(int i=1;i<=N; i)
cin>>v[i]>>w[i];
vector<vector<int>> f;
f.resize(N 1);
for(auto& x:f)
x.resize(V 1);
//上面都多1个是为了更好的表达
for(int i=1;i<=N; i)
{
for(int j=1;j<=V; j)
{
f[i][j]=f[i-1][j];//把前i-1物品的最大值传递给前i物品
if(j>=v[i])//说明可能装下这个，如果装的下，他就是最大值，但是不能求出，要进转化
f[i][j]=max(f[i][j],f[i-1][j-v[i]] w[i]);
}
}
cout<<f[N][V]<<endl;
return 0;
}优化：
代码语言：javascript复制cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int V,N;
cin>>V>>N;
vector<int> v(N 1),w(N 1);
for(int i=1;i<=N; i)
cin>>v[i]>>w[i];
vector<int> f;
f.resize(V 1);
for(int i=1;i<=N; i)
{
for(int j=V;j>=v[i];--j)
{
f[j]=max(f[j],f[j-v[i]] w[i]);
}
}
cout<<f[V]<<endl;
return 0;
}优化解释
为什么可以向上面那样优化呢？
- 因为我们发现都选取不同的i的时候，上一层的空间就是被搁置的，没有被利用的，那么为什么我们不能用上一层的空间呢？
下面主要是解释循环体里面的代码； 之前的代码：
代码语言：javascript复制cpp for(int j=1;j<=V; j)
{
f[i][j]=f[i-1][j];//把前i-1物品的最大值传递给前i物品
if(j>=v[i])//说明可能装下这个，如果装的下，他就是最大值，但是不能求出，要进转化
f[i][j]=max(f[i][j],f[i-1][j-v[i]] w[i]);
}我们把2维缩成1维，即只用原来的一行，该行的j列表示从所有的物品中选取不超过j空间大小的最大价值。**记住： **每次内循环完成的时候，表示从i个物品中选取的结果完成
如果这样修改：错误的
代码语言：javascript复制cpp for(int j=1;j<=V; j)
{
if(j>=v[i])
f[j]=max(f[j],f[j-v[i]] w[i]);//这里等价与f[i][j]=max(f[i][j],f[i-1][j-v[i]] w[i]);但是这个公式可能会改变上一层的最大值。
}怎么解决呢？倒着来，
代码语言：javascript复制cpp for(int j=V;j>=v[i];--j)//关键是V的问题，才使下面的方程可以进行转换
{
f[j]=max(f[j],f[j-v[i]] w[i]);//小括号里面的f[j]，是上一层的，但是可以理解为这一层的，把上一层的最大值给给了这一层，后面的参数是这一层的，需要转换。f[i][j]=max(f[i][j],f[i-1][j-v[i]] w[i]);
}
