完全背包问题
思路
这里只提一嘴状态转移方程的一个优化,优化后可以减少一个循环,降低时间复杂度
优化方法如下:
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w, .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w, f[i-1,j-2v]+2w , .....)
通过上述比较,可以得到 f[ i ][ j ] = max(f[ i - 1 ][ j ],f[ i ][ j - v ] + w)
代码里面的细节可以自己思考
不优化的代码(也能ac)
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1e3+10;
typedef pair<int, int> PII;
PII a[N];
int f[N],n,v;
int main()
{
cin>>n>>v;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
for(int i=1;i<=n;i++)
for(int j=v;j>=1;j--)
for(int k=0;k*a[i].x<=j;k++)
f[j]=max(f[j],f[j-k*a[i].x]+k*a[i].y);
cout<<f[v]<<endl;
return 0;
}
优化后的代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int n,v,f[N];
typedef pair<int,int> PII;
PII a[N];
int main()
{
cin>>n>>v;
for(int i=1;i<=n;i++)
cin>>a[i].first>>a[i].second;
for(int i=1;i<=n;i++)
for(int j=a[i].first;j<=v;j++)
f[j]=max(f[j],f[j-a[i].first]+a[i].second);
cout<<f[v]<<endl;
return 0;
}