01背包代码:
include[HTML_REMOVED]
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
int n,m;
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(v[i]<=j){
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
}
完全背包代码:
include[HTML_REMOVED]
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
int n,m;
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(v[i]<=j){
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
}
区别仅仅是
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
完全背包还是i 01背包是i-1
i代表我还可以选我自己,不把自己排除在外
选了我自己之后,还是按照包含我自己的状态去转移。
i-1代表选了我时候,按照排除我之后,按照之前的状态去转移。
强啊 。大佬