题目描述
blablabla
样例
输入
4 5
1 2
2 4
3 4
4 5
输出
8
算法1
(朴素版) $O(n^2)$
状态表示:f[i,j]
集合:所有前i个物品中选,且总体积不超过j;
属性:max;
状态计算(集合的划分):
对于f[i,j],分成两部分:
1:不选第i个物品(那么就是在前i-1个物品当中选)表示为f[i-1,j];
2:选第i个物品,现在已经确定选第i个物品,那么就是在前i-1个物品基础上再选第i个物品,
所以要把第i个物品的体积留出来,然后再加上第i个物品的价值。表示为f[i-1][j-v[i]]+w[i];
最终:由于求的是最大值,所以把两种情况比较得出最大值即可,最终整个的结果也就是f[n][m];(在前n个物品中选,体积不超过m的最大值);
时间复杂度
两重循环
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[1010];//存每个物品的体积
int w[1010];//存每个物品的价值
int f[1010][1010];//在前i个物品中,总体积不超过j;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)//这里的下标从1开始,因为下面有i-1,所以从1开始不会出现越界
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)//体积由0,1,2,3...m
{
f[i][j]=f[i-1][j];//第一种情况,当不选第i个物品
if(j>=v[i])//选第i个物品的前提是,当前背包可以装得下该物品,所以要判断
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); //选第i个物品就要留出它的空间,最后是两种情况的最大值。
}//这里的max里的f[i][j],是有上面更新来的,所以写成f[i-1][j],应该也可以,刚试了一下可以过。
}
printf("%d\n",f[n][m]);
return 0;
}
算法2
(优化成一维) $O(n^2)$
可以优化成一维的原因是:在而二维中,每次计算i,只与i-1有关,也就是只跟上一次有关,
故可以优化成一维(根据滚动数组),这里我也不太清楚关于滚动数组的。
要注意,在变成一维,判断在i行中,需要用的是i-1行的,还是第i行的(有可能是i行的,列数是前面的)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[1010];
int w[1010];
int f[1010];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)//这里为什么是倒着来的,就是因为,如果不是倒着来,那么用的f[j-v[i]],就是第i行的,因为,`j-v[i]`<`j`,所以,f[j-v[i]],在之前就已经计算过了,那么倒着来,就没有就算过f[j-v[i]],然后用的就是i-1行的。
//这里的可以改成>=当前V[i];
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
printf("%d\n",f[m]);
return 0;
}