NO.1 01背包问题
动态规划是我们c++学习中不可避免且相对棘手的问题,正所谓,吾后院有枇杷树,初学动规时手植也,今已亭亭如盖矣…,动规最大的优点是以空间为代价,节省时间,从某种角度说,他是递归的超进化。
在普通的递归中,我们如果要算出f(n+1),那我们必然要先求出f(n),而要求f(n),就要求f(n-1),而要求f(n-1),就要......(不断的重复重复再重复,吧啦吧啦),这么操作实在是too young too naive,太傻太天真。假设有这么一种情况,当我们要求f(n+1),时,f(n)的数据已将早早的被我们储存了,而动态规划就能够实现这样皆大欢喜的事。
动态规划中一般用数组为工具来实现。
我们将从01背包问题入手来直接进行介绍。
有 N件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i件物品的体积是 vi价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N行,每行两个整数 vi,wi,用空格隔开,分别表示第 i件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
(遗憾的是,尽管有01,但是没有我们想要的0和1…)
同志们,在解决这道题之前,重中之重是我们的解题思路,首先根据题目意思,我们创造一个二维数组f[i][j],i为物品类型,j为体积。
紧接着我们需要画一幅图,我称其为西方的耶路撒冷
解释一下,动态规划中的f[]数组的含义最为重要,也是最难想到的。在状态计算中,我们要牢记“最后”这一概念,因为我们是在选第i个,所以最后i类是我们要操心的,而不是前面的所有i-1个,此时我们有两个选择,选i个物品或不选。
如果不选i,则f[i][j]将变成f[i-1][j],从含以上来解释,即从前i-1个物品中选,总体积不超过j。
如果选i,则我们暂时的将i先排除在外,又因为总体积不超过j,所以式子变为f[i-1][j-v[i]],再把i变回来,式子最终为f[i-1][j-v[i]]+w[i]。
我们来看看代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N][N];
int v[N],w[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j-v[i]>=0)
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
return 0;
}
我们的一个简单01背包问题就解决了。
然而,我们还能对上式进行优化。将f[][]变为f[],这个降维打击是这样子的
我们发现,整道题都是f[i-1][],和f[i][]进行比较,那么其实我们只要把他们看作是一维数组的不断更新就行了
类似于上图,那我们此时就可以将表示行数的i给删掉,但是注意,我们一维数组的更新顺序是从小到大的,然而,f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i])中的i-1是需要的未更新的f[i-1][],所以出现矛盾,我们解决方法为将体积的for循环改为从大到小进行。
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N];
int v[N],w[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}