[数据结构与算法]动态规划之01背包问题

01背包可以解决什么类型的问题？

问题：一个小偷潜入了某个幸运儿的家中，小偷的包能够装的赃物有限，问如何拿才能使小偷获得的钱最多？（偷窃是犯法行为，我们不能模仿嗷）

遇到类似于这类问题时，我们就可以用01背包来解决。

状态方程

f[i,j] = Max{ f[i-1,j-Wight[i]]+value[i]( j >= W[i] ), f[i-1,j] }

f[i,j]表示从前i件物品中选取若干放在容量为j的背包中可以获得的最大价值。

其中Wight[i]表示第i件物品所占的空间，Value[i]表示第i件物品的价值。

注意：只有当j>=W[i]时，才能进行此操作，否则f[i][j] = f[i-1][j]。因为当背包装不下第i个物品时，f[i][j]的最大价值就是f[i-1][j]的最大价值（即第i个物品不选）。

上代码

#include <bits/stdc++.h>

using namespace std;

int f[1005][1005];
int w[1005];//物品所占的空间
int v[1005];//物品的价值
int n,m;//n个物品，背包的容量为m

int main()
{
	cin >> n >> m;
	for(int i=1; i<=n; i++)
	{
		cin >> w[i];
		v[i] = w[i];
	} 
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			if(j < w[i])
			{
				f[i][j] = f[i-1][j];
			}
			else
			{
				f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
			}
		}
	}
	cout << f[n][m];
	return 0;
}