01背包及其优化

基本01背包

假设一共有 n 件物品，物品有它的重量和价值，假设对于第i件物品来说，它的重量为vi，价值为wi。现在，如果你有一个大小为v的背包，请问你的背包能装的最大的物品价值是多少

思路：
1.最原始的想法是用二维数组存储这个背包，f [ i ] [ j ] 就表示，对于前 i 件物品，如果我的背包空间不超过 j 的时候的最大价值。
2.显然，对于一件物品，有两种情况，拿走或者不拿走：
（1）不拿走：f [ i ] [ j ]=f [ i -1 ][ j ] ,即与只有 前 i-1 种的时候一致
（2）拿走：f [ i ] [ j ]= f [ i-1 ][ j-v[ i ] ]+w[ i ] ,前 i-1 物品中，留出给第 i 的物品的位置的时候的最大值，加上这件物品的价值
3.注意：不拿走的情况有两种，一是：j < v[ i ] ,即位置不够的时候。二是：有位置，但是不是很划算
思路get以后就可以用代码实现了！

#include<bits/stdc++.h>
#define maxn 10004
int main()
{
int f[maxn][maxn];
int v[i];
int w[i];
int vv,n;
cin>>n>>v;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=v;j>=0;j--)
{
if(j>=v[i])
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
else
f[i][j]=f[i-1][j];
}
}
cout<<f[n][v]<<endl;
return 0;
}

01背包的优化

对于优化的理解：之前的每次更新都与i-1次，比v小的情况有关，因为第一个方法更新的时候，j >=v[ i ]，如果更新它是用容量不超过 j-w [ i ]的时候，所以要从后面更新，而且只用一个一维数组就可以了。

#include<bits/stdc++.h>
#define maxn 10004
int main()
{
int f[maxn];
int v[i];
int w[i];
int vv,n;
cin>>n>>v;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=v;j>=0;j--)
{
if(j>=v[i])
f[j]=max(f[j],f[j-v[i]]+w[i]]);
}
}
cout<<f[v]<<endl;
return 0;
}

再从一些细节优化一下

#include<bits/stdc++.h>
#define maxn 10004
int main()
{
int f[maxn];
int v[i];
int w[i];
int vv,n;
cin>>n>>v;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=v;j>=0;j--)
{
if(j>=v[i]&&f[j]<f[j-v[i]]+w[i]])
f[j]=f[j-v[i]]+w[i];
}
}
cout<<f[v]<<endl;
return 0;
}

最后

以上就是欢呼鸡翅为你收集整理的01背包及其优化的全部内容，希望文章能够帮你解决01背包及其优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。