[数据结构与算法]动态规划完全背包学习日记

10月15日

完全背包

#include<iostream>

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=1;j<=m;j++)
	{
		f[i][j]=f[i-1][j];
		for(int k=0;k*v[i]<=j;k++)
		{
			f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
		}
	}
	cout<<f[n][m]<<endl;
	return 0;
}

状态属性：在前i个物品中选取j的体积下的重量最大值

状态转移方程：和01背包异曲同工。首先在第i个物品不取的条件下：显然f[i][j]=f[i-1][j]。在第i个物品取得条件下：因为我们可以取，但我们不知要取多少个，所以枚举能取多少个，即为k的迭代。与当前状态太下取最大值即可。

优化：优化成O(n^2)

#include<iostream>
using namespace std;

const int N=10010;
int f[N][N];
int n,m;
int v[N],w[N];

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]) 
		f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
	}
	cout<<f[n][m]<<endl;
	return 0;
}

?只对优化的核心步骤进行解释

f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i],....,f[i-1][j-k*v[i]]+k*w[i])记红色为1部分

f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-2*v[i]]+w[i],...,f[i-1][j-k*v[i]]+（k-1）*w[i])记红色为2部分

显然1部分减去2部分为w[i]

所以，f[i][j]=max(f[i-1][j],f[j-v[]])

一维的优化

#include<iostream>

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=v[i];j<=m;j++)
	{
		f[j]=max(f[j],f[j-v[i]]+w[i]);
	}
	cout<<f[m]<<endl;
	return 0;
}

同01背包一样进行优化去掉一维，为什么该部分可以从v[i]开始，因为我们并不区分i-1和i的状态。